关于素数筛选法的问题？

御笔剑客

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

   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已经在前面遍历了，再遍历一遍也是徒劳。。