本文主要是介绍求素数的几个方法（最朴素版、n*sqrt(n)版、埃氏筛、欧拉筛），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最朴素版O(n^2)
#include <bits/stdc++.h>
using namespace std;
int n, cnt, prim[6000000];
bool flag; //true 表示质数
int main()
{scanf("%d", &n);for(int i=2; i<=n; ++i){flag=true; //默认为质数for(int j=2; j<=i-1; ++j){if(i%j==0){flag=false;break;}}if(flag){cnt++;prim[cnt]=i;}}printf("%d\n", cnt);for(int i=1; i<=cnt; ++i){printf("%d ", prim[i]);}return 0;
}
n*sqrt(n)版
#include <bits/stdc++.h>
using namespace std;
int n, cnt, prim[6000000];
bool flag; //true 表示质数
int main()
{scanf("%d", &n);for(int i=2; i<=n; ++i){flag=true; //默认为质数for(int j=2; j<=sqrt(i); ++j){if(i%j==0){flag=false;break;}}if(flag){cnt++;prim[cnt]=i;}}printf("%d\n", cnt);for(int i=1; i<=cnt; ++i){printf("%d ", prim[i]);}return 0;
}
埃氏筛O(nlgn)
//埃氏筛求1-n内的所有质数
#include <bits/stdc++.h>
using namespace std;
int n;
bool a[10000001]; //初始化为false, 默认都是质数
int main()
{scanf("%d", &n);for(int i=2; i<=sqrt(n); ++i){ //从 if(a[i]==0){ //如果i是质数 for(int j=i; i*j<=n; ++j){a[i*j]=1;} }} for(int i=2; i<=n; ++i){if(a[i]==0){printf("%d\n", i);}} return 0;
}欧拉筛（线性筛）O(n)
P3383 【模板】线性筛素数
//欧拉筛
#include <bits/stdc++.h>
using namespace std;
int n, q, k, cnt, prim[10000010], v[100000010];
int main()
{scanf("%d %d", &n, &q);for(int i=2; i<=n; ++i){if(v[i]==0){ //如果i是质数v[i]=i; //i的最小质因数为i本身cnt++; //质数个数加一prim[cnt]=i; //存到质数数组中}//从小到大枚举当前求出的所有质数for(int j=1; j<=cnt; ++j){ //cnt为质数的个数//用当前的质数prim[j]乘以i去标记合数prim[j]*i//如果乘起来超了n了, 则不用继续往后枚举了//或者如果i的最小质因数小于质数prim[j],//说明prim[j]*i这个合数已经被i的最小质因数标记过了, 就没有必要继续尝试更大的数了if(prim[j]*i>n || v[i]<prim[j]){break;}v[i*prim[j]]=prim[j]; //标记合数 i*prim[j] 的最小质因数为prim[j]}}while(q--){scanf("%d", &k);printf("%d\n", prim[k]);}return 0;
}
空间优化版的欧拉筛
//空间优化版的欧拉筛
#include <bits/stdc++.h>
using namespace std;
int n, cnt, prim[6000000];
bool vis[100000010]; //false 表示质数
int main()
{scanf("%d", &n);for(int i=2; i<=n; ++i){if(vis[i]==0){ //如果i是质数cnt++; //质数个数加一prim[cnt]=i; //存到质数数组中}//从小到大枚举当前求出的所有质数for(int j=1; j<=cnt && prim[j]*i<=n; ++j){ //cnt为质数的个数//用当前的质数prim[j]乘以i去标记合数prim[j]*ivis[i*prim[j]]=1; //标记合数 i*prim[j], 它的最小质因数为prim[j]//prim[j]*i这个合数已经被i的质因数prim[j]标记过了, 就没有必要继续尝试更大的数了if(i%prim[j]==0){break;}}}cout << cnt << endl;for(int i=1; i<=cnt; ++i){cout << prim[i] << " ";}return 0;
}
这篇关于求素数的几个方法（最朴素版、n*sqrt(n)版、埃氏筛、欧拉筛）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
