关于素数筛选法的问题？
#include <cstdio>#include <cstdlib>
#include <cstring>
#define MAX 1000000000//定义一个数组长度
bool prime;//素数表
int main()
{
int i, j, count = 0;//count为计数器
memset(prime, true, sizeof(prime));//初始化，将prime数组全部都初始化为true
prime = prime = false; prime = true;//0，1都不是素数，所以为false，2是素数，所以为true
for(i = 2; i * i <= MAX; i ++)
{
if(prime)//如果没有被标记的话将它的倍数的数标记(标记就是将它赋值为false)
{
for(j = i + i; j <= MAX; j += i)//因为是从2开始的，所以j = i * i 就行了，最小的一个他的倍数的就是i * i了，不可能有比这个更小的了
prime = false;//标记为false
}
}
for(i = 2; i <= MAX; i ++)//遍历一下，找出所有的素数来
if(prime)
count ++;//如果没有被标记，计数器++
printf("count is :%d\n", count);
return 0;
}
for(i = 2; i * i <= MAX; i ++)为什么只需要遍历i<=sqrt(MAX)就行了呢？ 一个数学定理，已经被证明了的 好像是为了减少循环得次数，把效率提升。。。 本帖最后由 8306最硬 于 2018-3-25 15:05 编辑
如果我要你判断625 是不是素数，你用程序怎么判断。
是不是只要在625之内找出两数相乘等于他，就可以说他不是素数了。
这两个数最大是多少？就是sqrt(625) = 25啊。 之所以大于25都不用遍历了，是因为25已经是最大了。
如果你说5 * 125 = 625， 125就比25大，但是5已经在前面遍历了，再遍历一遍也是徒劳。。
页:
[1]