埃氏筛法:
对于每一个小于n的非负整数p,删去2p,3p,4p......,当处理完所有数后,还没有删除的就是素数.
想法:用a记录素数表,a[i]=1表示不是素数,a[i]=0表示是素数.
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int n,m,a[10000005],t;
int main()
{
a[1]=1;
cin>>n>>m;
int pd=sqrt(n+0.5);
for(int i=2;i<=pd;i++) if(!a[i])
for(int j=i*i;j<=n;j+=i) a[j]=1;
// for(int i=1;i<=100;i++)
// cout<<a[i]<<endl;
for(int i=1;i<=m;i++)
{
cin>>t;
if(a[t]==0) cout<<"Yes\n";
else cout<<"No\n";
}
return 0;
}
注意:1不是素数,需要特判!
原文：https://www.cnblogs.com/huaruoji/p/11707548.html