Sieve of Prime Number

如何判断一个数是不是质数，现在求区间 $[1,1e7]$ 内所有质数，学习「埃式筛法」和「欧拉筛法」之前，先介绍下暴力筛选。

可借此题验证下：204. 计数质数

1. 暴力筛选

0 表示质数，1 表示合数。

1
2
3
4
5
6
7
8
9
10
11
static final int N = 1e7 + 5;
int st[N]; // 初始化为0，0表示质数，1表示合数

for(int i = 2; i <= n; i++){
	for(int j = 2; j * j <= i; j++){ //试除法
		if(i % j == 0){
			st[i] = 1; // 合数，标记为1
            break;
		}
	}
}

2. 埃式筛法

这种方法无疑是最慢的，换一种思路：一个质数的倍数一定是合数。

所以假设 P 是质数，我们可以筛选掉区间 $[1,1e7]$ 中所有 P 的倍数。

为什么这样能筛去所有的合数呢，因为一个合数一定能被分解为几个质数的幂的乘积，并且这个数的质因子一定是小于它本身的，所以当我们从小到大将每个质数的倍数都筛去的话，当遍历到一个合数时，它一定已经被它的质因子给筛去了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <vector>

const int N = 1e7 + 5;
int st[N]; // st[i] == 1 表示 i 是合数；0 表示 i 是素数

void E_sieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (st[i] == 0) {
            for (int j = 2 * i; j <= n; j += i) {
                st[j] = 1; // j 是 i 的倍数，是合数，标记为 1
            }
        }
    }
}

我们还可以对其进行优化：

  • 我们会先筛 2 的所有倍数，然后筛 3 的所有倍数，但筛除3的倍数时，我们还是从 3 的 2 倍开始筛，其实 $3 * 2$ ，已经被 $2 * 3$ 时筛过了。又比如说筛 5 的倍数时，我们从 5 的 2 倍开始筛，但是 $5 * 2$ 会先被 $2 * 5$ 筛去，$5 * 3$ 会先被 $3 * 5$ 筛去，$5 * 4$ 会先被 $2 * 10$ 筛去，所以我们每一次只需要从 $i * i$ 开始筛，因为 $(2，3,…,i - 1)$ 倍已经被筛过了。
  • 另外，判断一个数 n 是不是质数，我们只需要判断 $[2,\sqrt{n}]$ 内有没有它的因子，在筛选合数时，我们也可以这样做，因为一个合数的最小质因子一定小于等于 $\sqrt{n}$。

优化后的埃式筛法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>

const int N = 1e7 + 5;
int st[N]; // st[i] == 1 表示 i 是合数，0 表示 i 是素数

void E_sieve(int n) {
    for (int i = 2; i <= n / i; i++) {
        if (st[i] == 0) {
            for (int j = i * i; j <= n; j += i) {
                st[j] = 1; // j 是 i 的倍数，标记为合数
            }
        }
    }
}

时间复杂度可以近似看成 $O(n)$

但是我们还可以更快，那就是欧拉筛，又称为线性筛。

3. 欧拉筛法/线性筛法

欧拉筛的核心思想就是确保每个合数只被最小质因数筛掉，或者说被合数的最大因子筛掉。

比如 $120 = 2^3 * 3 * 5$，120 会被 2 筛一次，3 筛一次，5 筛一次。

多做了两次不必要的操作，如何确保 120 只 2 筛选掉。

时间复杂度：$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>

const int N = 1e7 + 5;
int st[N];           // st[i] == 1 表示 i 是合数
int primes[N];       // 存所有质数
int cnt = 0;         // 质数的个数

void ola(int n) {
    for (int i = 2; i <= n; i++) {
        if (st[i] == 0) {
            primes[cnt++] = i; // i 是质数，加入 primes 数组
        }
        for (int j = 0; j < cnt && primes[j] <= n / i; j++) {
            st[primes[j] * i] = 1; 	// 标记合数
            if (i % primes[j] == 0) // 保证每个合数只被它的最小质因子筛一次
                break;
        }
    }
}
许可协议

本文由 Yikun Wu 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处

分享文章
✍️ Yikun Wu 已发表了 69 篇文章 · 总计 293k 字，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处

🌀 本站总访问量 次