【算法】欧拉筛找素数

思路

从2开始找 找到一个加入素数表中 在之后的每一个数与前面找到素数表中的素数相乘的积也不是质数(任意一个合数是一个质数与一个数的积)

---

例题

洛谷P3383：线性筛素数（可用埃筛做）

https://www.luogu.org/problemnew/show/P3383

代码：

#include<iostream> using namespace std; int n,m,k; int f[10000001],p[10000001];//f判断是不是质数 //p存素数表 int main() { cin>>n>>m; for(int i=2;i<=n;i++) { if(f[i]==0) p[++k]=i;//加入质数表 for(int j=1;j<=k;j++) { if(i*p[j]>n) break; f[i*p[j]]=1;//任意一个合数是一个质数与一个数的积 } } f[1]=1; f[0]=1;//0和1不是质数 for(int i=1;i<=m;i++) { int x; cin>>x; if(f[x]==0) cout<<"Yes"<<endl; else cout<<"No"<<endl; } }

转载于:https://www.cnblogs.com/BrokenString/p/9279531.html