1. Eratothenes筛法（埃及老头筛法）O(N log log N)
   埃及老头筛法的原理就是找素数，筛掉在N以内它所有的倍数

#include
    
     using namespace std;const int maxn=1e7;bool prime[maxn];int n,m;void Eratothenes(int n){    memset (prime,0,sizeof(prime));    prime[1]=1;//1非素非合    for(int i=2;i<=n;i++){        if(prime[i])continue;//若是合数，不筛(筛过了)        for(int j=i;j<=n/i;j++){            prime[i*j]=1;        }   //筛素数倍数    }}int main(){    scanf("%d%d",&n,&m);    Eratothenes(n);    for(int i=1;i<=m;i++){        int ask;        scanf("%d",&ask);        if(!prime[ask])            printf("Yes\n");        else             printf("No\n");    }    return 0;}
    

1. 欧拉线性筛 O(N)

/*    Name:Euler linear sieve method    Author: Jack    Date: 03/04/19 16:15    Description:       1.依次考虑2~N之间的每一个数i      2.若v[i]=i,说明i为素数，保存在prime[]里      3.扫描不大于v[i]的每个素数p，令v[i*p]=p。        explain:          Because v[i]>p          so the least prime factor(因数) of i*p = p;  */#include
    
     using namespace std;const int maxn=1e7;int prime[maxn],v[maxn];//v[i]为 [i]的最小质因子 bool bucket[maxn];int n,m;void Eratothenes(int n){    int cnt=0;//素数数量     memset (prime,0,sizeof(prime));    memset (v,0,sizeof(v));    for(int i=2;i<=n;i++){        if(v[i]==0){            v[i]=i;            prime[++cnt]=i;            bucket[i]=1;        }        for(int j=1;j<=m;j++){            if(prime[j]>v[i]||prime[j]>n/i)break;            v[i*prime[j]]=prime[j];        }    } }int main(){    scanf("%d%d",&n,&m);    Eratothenes(n);    for(int i=1;i<=m;i++){        int ask;        scanf("%d",&ask);        if(bucket[ask])            printf("Yes\n");        else             printf("No\n");    }    return 0;}