质数检测

 1 #include<cstdio>
 2 const int maxn=40000;
 3 int n,a,b;
 4 int s[maxn],m;
 5 bool p,v[maxn+10];
 6 int main(){
 7     for(int i=2;i<=maxn;i++)
 8     if(!v[i]){
 9         s[m++]=i;a=i+i;
10         while(a<maxn){v[a]=1;a+=i;}
11     }
12     scanf("%d",&n);
13     for(int i=1;i<=n;i++){
14         scanf("%d",&a);
15         b=p=0;
16         while(s[b]*s[b]<=a&&b<m)
17         if(a%s[b++]==0){printf("NO\n");p=1;break;} 
18         if(!p) printf("YES\n");
19     }
20     return 0;
21 }