素数筛选的学习

素数筛选的学习"/>

素数筛选的学习

快速筛选素数方法

筛选2-N素数有很多方法，最一般的方法就是利用素数的定义也就是利用素数只能被本身和1整除的性质进行筛选。但是这个方法效率太低，不建议使用这个方法。

有这麽一种方法，好像叫做爱拉托逊斯筛选法（我也不是很清楚）

它的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。（来自百度百科）

代码如下：

for (int i=2;i<=n;i++){if(a[i]==0){for (int j=2*i;j<=n;j+=i)a[j]=1;}}

这个其实还是可以优化的，仔细想想这里面有重复筛选的情况，比如6，它就是2*3，但是筛选的时候筛选了2次，因为它既是2的倍数，也是3的倍数。所以这个代码还可以进一步优化。

代码如下：

int pr[2000005];
void is_suu(int n)
{int m=sqrt (double(n+0.5));memset (pr,0,sizeof(pr));for (int i=2;i<=m;i++){if(pr[i]==0){for (int j=i*i;j<=n;j+=i)pr[j]=1;}}for (int i=2;i<=n;i++)if(!pr[i])printf("%d ",i);printf("\n");
}

题目
.php?pid=187

转自