当前位置：首页 > article >正文

线性欧拉筛

article 2026/2/7 7:54:13

线性筛：高效求解素数

在数论中，素数的筛选是一个经典的问题。最常见的素数筛选方法是埃拉托斯特尼筛法，其时间复杂度为 $O(n\log \log n)$ ，非常适合求解小范围内的素数。随着问题规模的增大，传统的埃拉托斯特尼筛法可能会遇到效率瓶颈，因此线性筛（Linear Sieve）作为一种优化算法应运而生，它通过减少不必要的计算，优化了素数筛选的过程，具有 $O (n)$ 的时间复杂度。

本文将详细介绍线性筛法，并通过代码实现和分析，帮助你更好地理解其原理和应用。

1. 线性筛法的原理

线性筛法的核心思想是：通过直接利用已筛选出的素数来筛去合数，而避免像埃拉托斯特尼筛法中那样重复筛选已经合数的数。具体来说，我们通过对每个数 $i$ 判断它是否为素数，若是素数，则标记它的倍数为合数。关键的优化点在于：每个素数 $p$ 只会在第一次筛选其倍数时参与筛选。

1.1 线性筛法的步骤

初始化：准备一个布尔数组 is_prime[] 来标记每个数是否为素数，初始时所有数都标记为素数。
筛选过程：
- 从小到大遍历每个数 $i$ 。
- 如果 $i$ 是素数，则标记它的倍数为合数。
- 在标记倍数时，确保每个素数 $p$ 只参与标记一次 $\times p, p \times (p+1), \dots$ ，而不会重复标记。

1.2 线性筛的特点

时间复杂度： $O (n)$ ，因为每个素数只参与一次倍数的筛选。
空间复杂度： $O (n)$ ，需要一个大小为 $n$ 的布尔数组来记录素数信息。
效率：相对于传统的埃拉托斯特尼筛法，线性筛在处理大量数据时更为高效，避免了不必要的重复操作。

2.示例图解（n=20为例）

当前数 (i)	是否质数？	筛除的数 (i×primes[j])	质数列表 (primes)	说明
1	❌ 否	—	`[]`	1 不是质数，跳过。
2	✅ 是	`2×2=4`	`[2]`	首次遇到 2，加入质数列表，并筛除 `2×2=4`。
3	✅ 是	`3×2=6`, `3×3=9`	`[2, 3]`	首次遇到 3，加入质数列表，依次筛除 `3×2=6` 和 `3×3=9`。
4	❌ 否	`4×2=8`	`[2, 3]`	4 被 2 整除，仅筛除 `4×2=8`，之后停止（因为 `4%2==0`）。
5	✅ 是	`5×2=10`, `5×3=15`, `5×5=25`	`[2, 3, 5]`	首次遇到 5，加入质数列表，筛除 `10,15`，`25>20` 停止。
6	❌ 否	`6×2=12`	`[2, 3, 5]`	6 被 2 整除，仅筛除 `6×2=12`，之后停止。
7	✅ 是	`7×2=14`, `7×3=21`, `7×5=35`	`[2, 3, 5, 7]`	首次遇到 7，加入质数列表，筛除 `14`，`21>20` 停止。
8	❌ 否	`8×2=16`	`[2, 3, 5, 7]`	8 被 2 整除，仅筛除 `8×2=16`，之后停止。
9	❌ 否	`9×2=18`, `9×3=27`	`[2, 3, 5, 7]`	9 被 3 整除，筛除 `18`，`27>20` 停止。
10	❌ 否	`10×2=20`	`[2, 3, 5, 7]`	10 被 2 整除，仅筛除 `10×2=20`，之后停止。
11	✅ 是	`11×2=22`, `11×3=33`, `11×5=55`	`[2, 3, 5, 7, 11]`	首次遇到 11，加入质数列表，但所有乘积 `>20`，直接跳过筛除。
12	❌ 否	`12×2=24`	`[2, 3, 5, 7, 11]`	12 被 2 整除，仅筛除 `12×2=24`（`24>20` 实际不操作），之后停止。
13	✅ 是	`13×2=26`, `13×3=39`	`[2, 3, 5, 7, 11, 13]`	首次遇到 13，加入质数列表，所有乘积 `>20`，跳过筛除。
14	❌ 否	`14×2=28`	`[2, 3, 5, 7, 11, 13]`	14 被 2 整除，`28>20` 不操作，直接停止。
15	❌ 否	`15×2=30`, `15×3=45`	`[2, 3, 5, 7, 11, 13]`	15 被 3 整除，所有乘积 `>20`，跳过筛除。
16	❌ 否	`16×2=32`	`[2, 3, 5, 7, 11, 13]`	16 被 2 整除，`32>20` 不操作，直接停止。
17	✅ 是	`17×2=34`, `17×3=51`	`[2, 3, 5, 7, 11, 13, 17]`	首次遇到 17，加入质数列表，所有乘积 `>20`，跳过筛除。
18	❌ 否	`18×2=36`, `18×3=54`	`[2, 3, 5, 7, 11, 13, 17]`	18 被 2 整除，所有乘积 `>20`，跳过筛除。
19	✅ 是	`19×2=38`, `19×3=57`	`[2, 3, 5, 7, 11, 13, 17, 19]`	首次遇到 19，加入质数列表，所有乘积 `>20`，跳过筛除。
20	❌ 否	`20×2=40`	`[2, 3, 5, 7, 11, 13, 17, 19]`	20 被 2 整除，`40>20` 不操作，直接停止。

最终结果
• 质数列表：[2, 3, 5, 7, 11, 13, 17, 19]
• 关键规则：

每个合数仅被最小质因数筛除一次（如 12 只会被 2×6 筛除，不会被 3×4 重复筛）。
终止条件：当 i×primes[j] > n 时停止筛除（如 5×5=25>20 直接跳过）。

3. 线性筛法的代码实现

推荐题目： 洛谷3383 线性筛
以下是使用 Python 实现的线性筛法代码：

def linear_sieve(n):# 创建一个布尔数组，用来标记每个数是否是素数is_prime = [True] * (n + 1)# 记录所有的素数primes = []# 从2开始筛选for i in range(2, n + 1):if is_prime[i]:primes.append(i)# 遍历所有素数的倍数for p in primes:if i * p > n:  # 超过范围，停止breakis_prime[i * p] = Falseif i % p == 0:  # 保证每个素数只参与标记一次breakreturn primes# 测试
n = 30
primes = linear_sieve(n)
print(f"小于等于 {n} 的所有素数是：", primes)

2.1 代码解析

is_prime[]：布尔数组，用来记录从 $2$ 到 $n$ 的每个数是否为素数。初始化时设为 True，表示所有数默认是素数。
primes[]：用于存储所有的素数。
主循环：从 $2$ 开始，逐个判断每个数是否为素数。如果是素数，就将它的所有倍数标记为合数。
内循环：遍历已经找到的素数列表，筛去它们的倍数。由于线性筛法中每个素数只参与标记一次倍数，因此避免了重复计算。

2.2 示例输出

输入：

n = 30

输出：

小于等于 30 的所有素数是： [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

3. 线性筛法的优势与应用

3.1 优势

时间复杂度优化：传统的埃拉托斯特尼筛法在筛选过程中会重复筛除一些合数，而线性筛法保证每个素数只参与标记一次，从而避免了重复计算。
空间复杂度低：与其他优化算法（如线性筛的空间复杂度为 $O (n)$ ）相比，线性筛方法的空间利用相对较高，能够在更大的范围内处理素数问题。

3.2 应用场景

素数生成：当需要生成一个区间内的所有素数时，线性筛法提供了高效的算法。
区间素数筛选：在一些区间范围内筛选素数时，可以利用线性筛法进行优化。
数学问题：在数论、密码学等领域中，素数的筛选是常见的操作，而线性筛法能够提供高效的解法。

4. 线性筛法的优化

线性筛法的核心思想就是减少不必要的筛选，并利用已经筛选出的素数来避免重复工作。虽然它已经比传统的埃拉托斯特尼筛法更高效，但在一些实际场景下，仍然可以通过以下方式进行进一步优化：

优化内循环：内循环只需要检查当前素数 $p$ 是否小于等于当前数的平方根，避免多余的循环。
使用更紧凑的数据结构：通过位运算等方式优化布尔数组的存储，进一步节省空间。

5. 总结

线性筛法是一种高效的素数筛选算法，具有 $O (n)$ 的时间复杂度，相较于传统的埃拉托斯特尼筛法，避免了重复计算，能够更快速地生成素数。其在大规模素数筛选和数论问题中具有广泛应用，尤其在需要处理大范围素数时，线性筛法无疑是一种非常有效的工具。

通过对线性筛法的深入理解与实现，我们能够更好地应对需要高效素数筛选的各种问题，并在实践中提供优异的性能表现。