思路
从 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;
- }
- }
来源: http://www.bubuko.com/infodetail-2676556.html