筛选法（埃氏筛法)C++

输入N个整数M，判断它们是否为质数。如果是输出“YES”，否则输出“NO”。（1<=n<=10000）

输入格式

第一行为N，第2～n+1行每行为一个正整数M。（1<=M<=1000000）

输出格式

每行分别是“YES”或者“NO”。

输入/输出例子1

输入：3 
8 
9 
13 

输出：NO 
NO 
YES

样例解释

无

埃氏筛法:

#include<bits/stdc++.h>
using namespace std;
int n,a[1000005],m;
int main(){cin>>n;a[1]=1,a[0]=1;for(int i=2;i*i<=1000000;i++){if(a[i]==0)for(int j=i+i;j<=1000000;j+=i)a[j]=1;}for(int i=1;i<=n;i++){cin>>m;if(a[m]==0)cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
}