我是靠谱客的博主 激情抽屉,这篇文章主要介绍质数(素数)的筛法质数(素数)的三种筛法,现在分享给大家,希望可以做个参考。

质数(素数)的三种筛法

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

朴素筛法 O(n log ⁡ n log n logn)

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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 log log ⁡ n log n logn)

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

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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)。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#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; }

最后

以上就是激情抽屉最近收集整理的关于质数(素数)的筛法质数(素数)的三种筛法的全部内容,更多相关质数(素数)内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(99)

评论列表共有 0 条评论

立即
投稿
返回
顶部