埃氏筛：高效求解素数的经典算法#

在算法题中，我们经常会遇到这样的问题：

给定一个正整数 n，求出 1 ~ n 中所有的素数。

最直接的做法是：对每个数 x，判断它是否只能被 1 和自身整除。但如果对每个数都从 2 试除到 sqrt(x)，整体复杂度会比较高。

这时，经典的 埃氏筛 就派上用场了。

什么是埃氏筛？#

埃氏筛，全称 埃拉托色尼筛法，是一种用于快速筛选素数的算法。

它的核心思想很简单：

如果一个数是素数，那么它的倍数一定不是素数。

例如：

2 是素数，那么 4, 6, 8, 10... 都不是素数
3 是素数，那么 6, 9, 12, 15... 都不是素数
5 是素数，那么 10, 15, 20, 25... 都不是素数

通过不断标记素数的倍数，我们就能筛掉所有合数，剩下的就是素数。

算法过程#

假设我们要求 1 ~ n 中的所有素数。

创建一个布尔数组 is_prime，初始认为所有数都是素数。
将 0 和 1 标记为非素数。
从 2 开始遍历到 sqrt(n)。
如果当前数 i 仍然是素数，就把 i 的所有倍数标记为非素数。
最后数组中仍然为 True 的下标就是素数。

为什么从 `i * i` 开始标记？#

很多实现中会这样写：

1
for j in range(i * i, n + 1, i):

而不是从 2 * i 开始。

原因是：

对于素数 i，小于 i * i 的倍数已经被更小的素数筛过了。

例如，当 i = 5 时：

10 = 2 * 5，已经被 2 筛过
15 = 3 * 5，已经被 3 筛过
20 = 4 * 5，已经被 2 筛过

所以从 25 开始即可。

Python 代码实现#

1
def sieve(n: int) -> list[int]:
2
    if n < 2:
3
        return []
4

5
    is_prime = [True] * (n + 1)
6
    is_prime[0] = False
7
    is_prime[1] = False
8

9
    for i in range(2, int(n ** 0.5) + 1):
10
        if is_prime[i]:
11
            for j in range(i * i, n + 1, i):
12
                is_prime[j] = False
13

14
    return [i for i in range(2, n + 1) if is_prime[i]]
15

16

17
if __name__ == "__main__":
18
    print(sieve(50))

输出结果：

1
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

代码解析#

1. 初始化素数数组#

1
is_prime = [True] * (n + 1)
2
is_prime[0] = False
3
is_prime[1] = False

这里用 is_prime[i] 表示数字 i 是否为素数。

一开始先假设所有数都是素数，然后再把 0 和 1 标记为非素数。

2. 遍历可能的因子#

1
for i in range(2, int(n ** 0.5) + 1):

外层循环只需要遍历到 sqrt(n)。

如果一个合数存在大于 sqrt(n) 的因子，那么它一定也存在一个小于等于 sqrt(n) 的因子。因此，只要筛到平方根即可。

3. 标记倍数#

1
for j in range(i * i, n + 1, i):
2
    is_prime[j] = False

如果 i 是素数，就将 i 的倍数全部标记为非素数。

这里从 i * i 开始，是因为更小的倍数已经在之前被筛过了。

4. 收集答案#

1
return [i for i in range(2, n + 1) if is_prime[i]]

最后遍历 is_prime 数组，把仍然为 True 的数字收集起来，就是 1 ~ n 中所有的素数。

复杂度分析#

埃氏筛的时间复杂度是：

1
O(n log log n)

空间复杂度是：

1
O(n)

相比逐个判断素数的做法，埃氏筛在需要求出大量素数时效率非常高。

常见细节#

1. `0` 和 `1` 不是素数#

素数定义是大于 1，并且只能被 1 和自身整除的整数。

因此：

1
is_prime[0] = False
2
is_prime[1] = False

是必要的。

2. 外层循环只需要到 `sqrt(n)`#

写成：

1
for i in range(2, int(n ** 0.5) + 1):

即可。

如果不想使用浮点数，也可以写成：

1
i = 2
2
while i * i <= n:
3
    ...
4
    i += 1

3. `n < 2` 时直接返回空列表#

因为小于 2 的范围内不存在素数：

1
if n < 2:
2
    return []

总结#

埃氏筛是求素数问题中非常经典的算法。

它不是一个一个判断每个数是不是素数，而是反过来利用素数去筛掉它的倍数。这个思想非常重要：通过批量排除合数，快速得到所有素数。

适合使用埃氏筛的场景包括：

求 1 ~ n 中所有素数
统计素数个数
预处理素数表
多次查询某个数是否为素数

如果题目中出现“大范围内求素数”或“多次判断素数”，埃氏筛通常就是首选方案。