经典指数          
原因
1887
浏览数
0
收藏数
 

以下代码是用来计算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; }

     举报   纠错  
 
切换
1 个答案

算法思想:

任何整数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中是否包含链表中已经存在的素数,,没有,该数就是素数!!

 
切换
撰写答案