筛素数

1.判断一个数是否为素数

　　对于n

　　i从2到sqrt(n)依次尝试若不存在i使得n%i==0则为素数

　　反之则不是

　　时间复杂度sqrt(n)

　　或者

　　有结论:大于等于5的素数可以表示成6*n-1或6*n+1

　　所以可以用该方法来判断素数

void isprime(int x){
    if(x==0||x==1)return 0;
    if(x==2||x==3)return 1;
    if(x%6!=1&&x%6!=5)return 0;
    if(x==4)return 0;
    for(int i=5;i*i<=n;i+=6){
        if(x%i==0||x%(i+2)==0)return 0;
    }
    return 1;
}

2.埃氏筛法

　　素数的倍数一定不是素数

　　由此可以筛素数

void tprime(){
    memset(p,true,sizeof p);
    p[0]=p[1]=0;
    p[2]=1;
    for(int i=2;i<=maxn;i++){
        if(p[i]){
            for(int j=2*i;j<=maxn;j+=i){
                p[j]=0;
            }
        }
    }
}

3.欧拉筛法

　　每个数只会被它最小的质因子筛去

　　背过代码就行了（逃

　

void oprime(){
    p[1]=p[0]=0;
    for(int i=2;i<=maxn;i++){
        if(!vis[i]){
            p[++tot]=i;
        }
        for(int j=1;j<=tot&&p[j]*i<=maxn;j++){
            vis[p[j]*i]=1;
            if(i%p[j]==0)break;
        }
    }
}