关于素数筛选法的问题？

御笔剑客

1. #include <cstdio>
   
2. #include <cstdlib>
   
3. #include <cstring>
   
4. #define MAX 1000000000//定义一个数组长度
   
5. bool prime[MAX + 1];//素数表
   
6. int main()
   
7. {
   
8.     int i, j, count = 0;//count为计数器
   
9.     memset(prime, true, sizeof(prime));//初始化，将prime数组全部都初始化为true
   
10.     prime[0] = prime[1] = false; prime[2] = true;//0，1都不是素数，所以为false，2是素数，所以为true
    
11.     for(i = 2; i * i <= MAX; i ++)
    
12.    
    
13.     {
    
14.         if(prime[i])//如果没有被标记的话将它的倍数的数标记(标记就是将它赋值为false)
    
15.         {
    
16.             for(j = i + i; j <= MAX; j += i)//因为是从2开始的，所以j = i * i 就行了，最小的一个他的倍数的就是i * i了，不可能有比这个更小的了
    
17.                 prime[j] = false;//标记为false
    
18.         }
    
19.     }
    
20.     for(i = 2; i <= MAX; i ++)//遍历一下，找出所有的素数来
    
21.         if(prime[i])
    
22.                 count ++;//如果没有被标记，计数器++
    
23.     printf("count is :%d\n", count);
    
24.     return 0;
    
25. }

复制代码

   for(i = 2; i * i <= MAX; i ++)为什么只需要遍历i<=sqrt(MAX)就行了呢？

BngThea

一个数学定理，已经被证明了的

Dr丶温

好像是为了减少循环得次数，把效率提升。。。

8306最硬

如果我要你判断625 是不是素数，你用程序怎么判断。
是不是只要在625之内找出两数相乘等于他，就可以说他不是素数了。
这两个数最大是多少？就是sqrt(625) = 25啊。 之所以大于25都不用遍历了，是因为25已经是最大了。

如果你说5 * 125 = 625， 125就比25大，但是5已经在前面遍历了，再遍历一遍也是徒劳。。