以下代码是用来计算100以内的素数的个数,请把相应的空填上。 struct prime_number_node { int prime_number; prime_number_node *next; }; int calc_prime_number( ) { prime_number_node *list_head = new prime_number_node( ); list_head - > next = NULL; list_head - > prime_number = 2; prime_number_node *list_tail = list_head; for (int number = 3 ; number & lt; 100 ; number++) { int remainder; prime_number_node *cur_node_ptr = list_head; while (cur_node_ptr != NULL) { remainder = number % cur_node_ptr - > prime_number; if (remainder == 0) { 1 //1 } else { 2 //2 } } if (remainder != 0) { prime_number_node *new_node_ptr = new prime_number_node( ); new_node_ptr - > prime_number = number; new_node_ptr - > next = NULL; list_tail - > next = new_node_ptr; 3 //3 } } int result = 0; while (list_head != NULL) { result++; prime_number_node *temp_ptr = list_head; list_head = list_head - > next; 4 //4 } return result; }
算法思想:
任何整数n≥2都可以分解成若干质数(素数)的乘积,即
n=p1
×
p2
×
···
×
pr;
且这些质数的组成是唯一的.
在我们开始证明计算基本定理之前,先要做一些必要的解释.首先,如果n本身就是个质数,那么我们只能写成n=n,并且把它认定成一个独立数字的乘积.第二,当我们写出n=p1p2···pr时,并不意味着p1,p2,...,pr这些数都是不同的质数.比如,300=2×2×3×5×5.第三,所说的那个“唯一”指的是那些质数的组成是唯一的,而不是指排列顺序.如,12=2×2×3,12=2×3×2,12=3×2×2,但这些都视为同一种组成方式.
所以判断一正整数是不是素数,只要用该数对其之前的所有素数进行求余运算,余数为零,说明该数包含除了1和其本身之外的其他因数,不可能是素数,否则的话,该数就是素数。
所以程序中,对于每一个需要判定的数number,在for循环开始之前,cur_node_ptr指针都会被拉到链表的头指针处,之后用链表中已经存在的,比number要小的这些素数,一个一个的去除number,看number中是否包含链表中已经存在的素数,,没有,该数就是素数!!