【模板】埃筛

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn=10000010;
 5 int n,m,x;
 6 bool a[maxn];
 7 void read(int &k){
 8     k=0; int f=1; char c=getchar();
 9     while (c<‘0‘||c>‘9‘)c==‘-‘&&(f=-1),c=getchar();
10     while (‘0‘<=c&&c<=‘9‘)k=k*10+c-‘0‘,c=getchar();
11     k*=f;
12 }
13 int main(){
14     read(n); read(m);
15     a[1]=1;
16     for (int i=2;i*i<=n;i++) if (!a[i])
17         for (int j=i<<1;j<=n;j+=i) a[j]=1;
18     for (int i=1;i<=m;i++){
19         read(x); printf(a[x]?"No\n":"Yes\n");
20     }
21     return 0;
22 }