质数

判断单个素数

inline bool isprime(int x){
    if(x<2)return false;/*2以内不是质数*/
    int sq=sqrt(x)+1;
    for(int i=2;i<=sq;i++)if(x%i==0)return false;/*因子最多根号个，扫描每个因子*/
    return true;

}

埃氏筛

任意整数的倍数都不是倍数，标记这些倍数，没有被标记的就是质数，时间复杂度 \(O(N* \log\log N)\).

inline void sieve(int n){
    for(int i=2;i<=n;i++){
        if(!v[i])prime[++m]=i;/*没有被标记的是质数*/
        for(int j=i<<1;j<=n;j+=i)v[j]=1;/*标记当前数每个倍数*/
    }
}

线性筛，即欧拉筛

控制每个数只被标记一次，即被它的最小质因子标记。

inline void sieve(int n){
    for(int i=2;i<=n;i++){
        if(!v[i])prime[++m]=i,miv[i]=i;/*i的最小质因子是i*/
        for(int j=1;j<=m&&i*prime[j]<=n;j++){
            v[i*prime[j]]=1;
            miv[i*prime[j]]=prime[j];/*i*prime[j]的最小质因子是prime[j]*/
            if(i%prime[j]==0)break;/*当i中也含有质因子prime[j]时停止*/
        }
    }
}