本文共 1028 字，大约阅读时间需要 3 分钟。

 筛选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");}

 此方法避免了上述的情况。

还有一种筛选素数的方法

int isPrime(int n){    if(n<=1)        return 0;    if(n==2||n==3)        return 1;    if(n%6!=5&&n%6!=1)        return 0;    for(int i=5;i<=sqrt(n);i++)        if(n%i==0||n%(i+2)==0)        return 0;    return 1;}

具体例子可以看南阳oj 187.

链接如下：

也可以参考我写的哦。。。虽然很菜。。

转载地址：http://vjaen.baihongyu.com/