P3383 【模板】线性筛素数

欧拉筛O(n)

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,cnt,prime[10000002],v[10000002]; //prime:素数表 v:存某数的最小质因数
int main(){
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n;++i){
        if(!v[i]) prime[++cnt]=v[i]=i;
        for(int j=1;j<=cnt;++j){
            if(prime[j]>v[i]||prime[j]>n/i) break; //保证只能被更小的素数筛到
            v[prime[j]*i]=prime[j];
        }
    }
    for(int i=1;i<=m;++i){
        int q; scanf("%d",&q);
        if(v[q]==q) printf("Yes
");
        else printf("No
");
    }
    return 0;
}

当不需要求最小质因数，只需判断是否是质数时，用下列写法可以快2倍

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 10000002 
int n,m,pri[N],cct;bool v[N];
void findpri(){
    v[1]=1;
    for(int i=2;i<=n;++i){
        if(!v[i]) pri[++cct]=i;
        for(int j=1;j<=cct&&pri[j]*i<=n;++j)
            v[pri[j]*i]=1;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    findpri(); int q;
    for(int i=1;i<=m;++i){
        scanf("%d",&q);
        printf(v[q]?"No
":"Yes
");
    }return 0;
}

 1 void getphi(){
 2     phi[1]=1;
 3     for(int i=2;i<=n;++i){
 4         if(!v[i]) pri[++cnt]=i,phi[i]=i-1;
 5         for(int j=1;j<=cnt;++j){
 6             int t=i*pri[j];
 7             if(t>n) break;
 8             v[t]=1;
 9             if(i%pri[j]) phi[t]=phi[i]*(pri[j]-1); 
10             else{phi[t]=phi[i]*pri[j];break;}
11         }
12     }
13 }

拓展：筛欧拉函数

 1     mu[1]=1;
 2     for(int i=2;i<N;++i){
 3         if(!v[i]) pri[++pct]=i,mu[i]=-1;
 4         for(int j=1;j<=pct;++j){
 5             int tmp=i*pri[j];
 6             if(tmp>=N) break;
 7             v[tmp]=1;
 8             if(i%pri[j]) mu[tmp]=-mu[i];
 9             else break;
10         }
11     }

拓展：筛莫比乌斯函数