luogu_3383 【模板】线性筛素数

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m,cnt,prime[10000010],noprime[10000010];
 4 
 5 int main(){
 6     scanf("%d%d",&n,&m);
 7     prime[1]=2;
 8     noprime[1]=1;
 9     for(int i=2;i<=n;i++){
10         if(!noprime[i])prime[++cnt]=i;
11         for(int j=1;j<=cnt && prime[i]<=i && i*prime[j]<=n;j++){
12             noprime[i*prime[j]]=1;
13             if(i%prime[j]==0)break;
14         }
15     }
16     while(m--){
17         int a;
18         scanf("%d",&a);
19         if(!noprime[a])puts("Yes");
20         else puts("No");
21     }
22     return 0;
23 }