线性筛法素数判断优化

判断素数：

普通的就不说了

一种更高效的做法：

结论是：大于等于5的质数一定和6的倍数相邻

令

可以看到，不在6的倍数两侧，即

所以它们一定不是素数，再除去

所以，基于以上条件，我们假如要判定的数为

但是

即循环的步长可以定为

bool Is_prime(int n)
{
    if(n==1) return false;
    if(n==2||n==3) return true;
    if(n%6!=1&&n%6!=5) return false;
    for(register int i=5;i*i<=n;i+=6)
        if(n%i==0||n%(i+2)==0) return false;
    return true;
}

复杂度为：o（ sqrt（n）/3 ）

1埃拉托斯特尼筛法（最基本方法)

思想：素数的倍数一定不是素数复杂度：O(nloglogn)

void prime(){
    //1表示不是素数，0表示是素数 
    a[1]=1;//1不是素数 
    for(int i=2;i*i<=k;i++){//枚举到k开方 
        if(a[i]==0){ 
            for(int j=i*i;j<=k;j+=i){
                //j从i平方开始，每次加i
                a[j]=1;//这些被穷举到的都不是素数 
            }
        }
    }
}

埃拉斯特尼筛法

通过上述代码，我们发现此方法还可以继续优化，因为上述的方法中，每一个有多组因数可能会被筛多次，例如：

#include<cstring>
#incldue<cmath>
const int MAXN=1000010;
bool prime[MAXN];
int Prime[MAXN];
int num=0;
void make_prime()
{
    memset(prime,true,sizeof(prime));
    prime[0]=prime[1]=false;
    for(int i=2;i<=MAXN;i++)
    {
        if(prime[i])
        {
            Prime[num++]=i;
        }
        for(int j=0;j<num&&i*Prime[j]<MAXN;j++)
        {
            prime[i*Prime[j]]=false;
            if(!(i%Prime[j]))
                break;
        }
    }
    return;
}

欧拉筛

这个方法可以保证每个和合数在

但是这个算法的弊端在于，为了判断一个大数是否是素数必须从从头开始扫描，而且空间代价也受不了，故不能离散的判断。

线性筛法 素数判断优化

线性筛法素数判断优化