质数（素数）的三种筛法

质数的判定：约数只有1和其本身的自然数。
现在给定一个数n，要求我们列出从1~n的质数。
思路：
我们先定义一个bool数组st[N],用st[1]~st[n]的下表分别对应1到n。不是质数的标为true，将其筛掉。
再用一个int数组prime[N]来存放质数。

朴素筛法 O(n$\log n$)

#include <iostream>
using namespace std;
const int N = 1000010;
int prime[N], cnt = 0;
bool st[N] = { false };
void get_prime(int x)
{
for (int i = 2; i <= x; i++)
{
if (!st[i]) prime[cnt++] = i;
/*如果st[i]为false,则i必定不是2~i-1
中任何一个数的倍数，故i必为质数*/
for (int j = 2 * i; j <= x; j += i) st[j] = true;
//则i的倍数一定不是质数，筛去
}
}
int main()
{
int n;
cin >> n;
get_prime(n);
for(int i = 0; i <= cnt; i++)
cout << prime[i] << ' ';
cout << endl;
return 0;
}

这种算法会将一个不是质数的数（合数）被重复筛选。如果这个合数有n个因子，则其会被筛去n-2次。我们可以通过减少筛选次数来优化算法。

埃式筛法 O(n$\log$$\log n$)

这里我们要先明白一个规律：
任意一个合数一定可以分解为一个质数与一个任意自然数t的乘积，即合数必有质数因子。
证明：一个合数n必定可以分为1和其本身的两个因子a和b。如果a和都不为质数，则a和b中任意一个都能继续往下分解。直到分解出质数因子为止。

#include <iostream>
using namespace std;
const int N = 1000010;
int prime[N], cnt = 0;
bool st[N] = { false };
void get_prime(int x)
{
for (int i = 2; i <= x; i++)
{
if (!st[i])
/*i不为1~i-1中任何一个质数的倍数，i无质数因子，故i为质数*/
{
prime[cnt++] = i;
//筛去所有含有此质数因子的数
for (int j = i; j <= x; j += i) st[j] = true;
}
}
}
int main()
{
int n;
cin >> n;
get_prime(n);
for(int i = 0; i <= cnt; i++)
cout << prime[i] << ' ';
cout << endl;
return 0;
}

我们让每个合数只能被其质数因子筛去，从而减少筛选次数。
但是一个合数有可能有好几个质数因子，因此有可能会被重复筛去。

欧拉筛法 O(n)

欧拉筛法也叫线性筛法。欧拉筛法能够保证每个数只会被其最小的质数因子筛去，这样每个合数只会被筛选一次，因此可以达到线性时间复杂度O(n)。

#include <iostream>
using namespace std;
const int N = 1000010;
int prime[N], cnt = 0;
bool st[N] = { false };
void get_prime(int x)
{
for (int i = 2; i <= x; i++)
{
if (!st[i]) prime[cnt++] = i;
for (int j = 0; prime[j] <= x / i && prime[j] <= i; j++)
//此时prime[j]最大元素为i。prime[j]<=i
//对于任意一个合数x，假设prime[j]为x最小质因子，
//当i<x/prime[j]时，x一定会被筛掉
{
st[prime[j]*i] = true;
//prime[j]<=i,prime[j]只须与比其大的数相乘来筛选即可。
//因为与比其小的数相乘的乘积的最小质数因子一定小于prime[j]
if (i % prime[j] == 0) break;
/*
1.i%prime[j] == 0, prime[j]定为i最小质因子，
prime[j]也定为prime[j]*i最小质因子
2.i%prime[j] != 0, prime[j]定小于i的所有质因子，
所以pj也为pj*i最小质因子。
接下来的prime[j+k]*i(k>0)
一定含有质数因子prime[j](i为prime[j]的倍数)，
因此prime[j+k]不是最小质数因子
跳出循环
*/
}
}
}
int main()
{
int n;
cin >> n;
get_prime(n);
for(int i = 0; i <= cnt; i++)
cout << prime[i] << ' ';
cout << endl;
return 0;
}

最后

以上就是激情抽屉为你收集整理的质数（素数）的筛法质数（素数）的三种筛法的全部内容，希望文章能够帮你解决质数（素数）的筛法质数（素数）的三种筛法所遇到的程序开发问题。

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