[简单实用] C/C++ 如何线性筛素数
题目描述
给定一个范围N (N<=1e7),你需要处理M (M<=5*1e5)个某数字是否为质数的询问(每个数字均在范围1~N内)
输入格式
第一行包含两个正整数N、M,分别表示查询的范围和查询的个数。
接下来M行每行包含一个不小于11且不大于N的整数,即询问该数是否为质数。
输出格式
输出包含M行,每行为Yes或No,即依次为每一个询问的结果。
样例
输入:
100 5
2 3 4 91 97
输出:
Yes
Yes
No
No
Yes
先把这范围内的素数都筛出来(欧拉筛法),然后匹配有没有即可。
筛法
1. 找一个素数
2. 筛掉除了那个素数本身的那个素数的倍数
3. 一直筛到上限为止
4. 找下一个未被筛掉的数,重复步骤1,2,3
5. 没有素数了就表示筛完了(其实筛到最大值/2就行了)
举个例子
全部初始化1(1表示有素数,0表示没有)
1变成0(1不是素数)
找到2,变成1。4,6,8,10,12,14,16,18,20变成0
找到3,变成1。6,9,12,15,18变成0(重复了无所谓)
以此类推
变成了如下所示的样子
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
附上此题完整代码,即筛法模版
#includeusing namespace std;int main(){ios::sync_with_stdio(0);cin.tie(0);bool pr[10000001];int k,m,n,s=0,x;cin>>n>>mpr[1]=false;for (int i=2;i<=n;i++)pr[i]=1;k=1;while (k<=n/2){while (!pr[k] && k<=n)k++;for (int i=k*2;i<=n;i=i+k)pr[i]=0;k++;}for (int i=1;i>x;if (pr[x])cout<<"Yes"<<endl;elsecout<<"No"<<endl;}return 0;}
https://blog.csdn.net/zeekliu/article/details/124104680