【筛质数】三种筛质数的方法

筛质数

朴素筛法

即是将每个数的倍数，例如
当i = 2，4 6 8 10 12 14会被筛去;
当i = 3, 6 9 12 15 会被筛去；

这里会出现重复筛出同一个数的情况,如6, 会被2和3同时筛一次

//朴素筛法 
#include<iostream>
using namespace std;
const int N = 1000010;
int primes[N], cnt;
bool st[N];
void get_primes(int n)
{
for(int i = 2; i <= n; i ++)
{
if(!st[i])
{
primes[cnt ++] = i;
}
for( int j = i + i; j <= n; j += i ) st[j] = true;
}
}
int main()
{
int n;
cin>>n;
get_primes(n);
for(int i = 0; i < cnt; i ++) cout<<primes[i]<<" ";
return 0;
}

埃氏筛法

即是在朴素筛法的基础上进行优化，他只会筛去素数的倍数
代码几乎相同, 只是将循环与质数套在一起

//埃氏筛法 
#include<iostream>
using namespace std;
const int N = 1000010;
int primes[N], cnt;
bool st[N];
void get_primes(int n)
{
for(int i = 2; i <= n; i ++)
{
if(!st[i])
{
primes[cnt ++] = i;
for( int j = i + i; j <= n; j += i ) st[j] = true;
}
}
}
int main()
{
int n;
cin>>n;
get_primes(n);
for(int i = 0; i < cnt; i ++) cout<<primes[i]<<" ";
return 0;
}

线性筛法

线性筛法会保证一个合数只会被它的最小质因子筛去，并且保证每个合数都会被筛掉, 复杂度仅为O(n)， 每个筛的数只会被一个质数筛掉

//朴素筛法 
#include<iostream>
using namespace std;
const int N = 1000010;
int primes[N], cnt;
bool st[N];
void get_primes(int n)
{
for(int i = 2; i <= n; i ++)
{
if(!st[i]) primes[cnt ++] = i;
for(int j = 0; primes[j] <= n / i; j ++)
{
st[primes[j] * i] = true;
if(i % primes[j] == 0) break;
}
}
}
int main()
{
int n;
cin>>n;
get_primes(n);
for(int i = 0; i < cnt; i ++) cout<<primes[i]<<" ";
return 0;
}

尾注: C++中的未定数组可由输入决定. 全局变量默认初始化为0

最后

以上就是伶俐煎蛋为你收集整理的【筛质数】三种筛质数的方法的全部内容，希望文章能够帮你解决【筛质数】三种筛质数的方法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。