1. 项目概述：为什么我们需要素数筛法？

在编程和算法竞赛中，判断一个数是否为素数，或者找出一定范围内的所有素数，是一个经典且高频的问题。新手可能会从最直观的“试除法”入手，即对于一个数 n，从 2 遍历到 √n，检查是否能被整除。这种方法对于单个数的判断尚可，但一旦问题变成“找出 1 到 100 万之间的所有素数”，其时间复杂度 O(n√n) 就完全无法接受了，计算量会大到程序几乎无法在合理时间内完成。这正是素数筛法（Sieve）大显身手的地方。筛法的核心思想不是去“判断”每个数，而是去“标记”和“排除”合数，从而高效地“筛”出素数。今天，我们就来深入拆解两种最经典、应用最广的筛法：埃拉托斯特尼筛法（简称埃氏筛）和欧拉筛（也称线性筛）。我会结合自己多年刷题和项目开发的经验，不仅讲清楚原理和代码，更会分享在实际应用中如何选择、优化以及避坑，让你彻底掌握这两种利器。

2. 算法核心思路与原理对比

理解两种筛法的根本差异，是正确选择和使用的关键。它们的目标一致，但实现路径和效率截然不同。

2.1 埃氏筛：直观高效的“批量标记”

埃氏筛的思路非常直观，像用筛子过滤沙子。我们假设一开始所有数都是“素数候选”。从最小的素数 2 开始，将其所有的倍数（4, 6, 8, 10...）标记为合数。然后，找到下一个未被标记的数（此时是3），它一定是素数（因为所有小于它的数的倍数都已检查过），再将 3 的所有倍数标记为合数。如此反复，直到处理完所有数。

其核心操作可以概括为：对于一个素数p，标记p * 2,p * 3,p * 4, ... 为合数。

为什么有效？因为任何一个合数n，都可以表示为n = p * q（p ≤ q）。当我们用最小的素因子p去筛选时，n必然会在遍历到p时被标记为合数。这就保证了所有合数都会被筛掉，剩下的就是素数。

埃氏筛的复杂度：其时间复杂度为 O(n log log n)。这个复杂度已经非常优秀，对于 n = 10^6（一百万）级别的问题绰绰有余，代码也极其简洁，是许多场景下的首选。

2.2 欧拉筛：追求极致的“线性筛”

埃氏筛虽然高效，但它有一个明显的“浪费”：一个合数可能会被它的多个素因子重复标记。例如，合数 12 = 2 * 6 = 3 * 4，在埃氏筛中，它既会被素数 2 标记（26），也会被素数 3 标记（34）。当数据范围n极大（例如 10^7 或更大）时，这种重复操作累积起来会成为性能瓶颈。

欧拉筛的诞生，就是为了解决这个问题，确保每个合数只被其最小的素因子标记一次，从而达到理论上的线性时间复杂度 O(n)。这是以略微复杂的逻辑为代价换来的极致效率。

欧拉筛的核心机制：

1. 维护一个素数列表primes。
2. 从小到大遍历每个整数i。
3. 对于每个i，用当前已知的素数primes[j]去尝试标记合数i * primes[j]。
4. 关键终止条件：当i % primes[j] == 0时，立即停止内层循环。

为什么这个终止条件如此重要？这正是保证每个合数只被筛一次的精髓所在。假设i % primes[j] == 0，即i = primes[j] * k。那么对于下一个素数primes[j+1]，要标记的合数是i * primes[j+1] = primes[j] * k * primes[j+1]。你会发现，这个合数的最小素因子是primes[j]，它本应在未来当i增长到k * primes[j+1]时，用primes[j]这个更小的素因子去标记。如果现在用primes[j+1]标记了，就造成了重复。因此，此时必须跳出循环。

3. 代码实现与逐行解析

理解了原理，我们来看代码。我会提供 Python 和 C++ 两种常见语言的实现，并加入详细注释和我的调试心得。

3.1 埃氏筛的实现与优化技巧

基础版本 Python 实现：

def sieve_eratosthenes(n): """ 埃氏筛法，返回小于 n 的所有素数列表。 """ is_prime = [True] * (n) # 初始化标记数组，假设所有数都是素数 is_prime[0] = is_prime[1] = False # 0 和 1 不是素数 # 只需遍历到 sqrt(n) for i in range(2, int(n ** 0.5) + 1): if is_prime[i]: # 如果 i 是素数 # 从 i*i 开始标记，因为 i*2, i*3, ..., i*(i-1) 已经被更小的素数标记过了 for j in range(i * i, n, i): is_prime[j] = False # 收集所有素数 primes = [i for i in range(2, n) if is_prime[i]] return primes # 示例：找出 100 以内的素数 primes = sieve_eratosthenes(100) print(primes[:20]) # 输出前20个素数

关键点解析与我的踩坑经验：

1. is_prime数组大小：通常创建长度为n的数组，下标对应数字本身。is_prime[i]为True表示i是素数。注意，这个数组通常不包含n本身，函数返回的是小于n的素数。
2. 外层循环终止条件int(n ** 0.5) + 1：这是最重要的优化之一。因为任何合数n必有一个因子 ≤ √n。所以，如果一个数没有被 ≤ √n 的素数筛掉，那它一定是素数。这大大减少了外层循环次数。
3. 内层循环起始点i * i：这是另一个关键优化。思考一下，对于素数i，它的倍数i*2,i*3, ...,i*(i-1)的最小素因子一定小于i（例如i*2的最小素因子是 2）。这些数在之前遍历更小的素数时（比如 2, 3, ...）就已经被标记过了。从i*i开始标记，避免了大量重复工作。
4. 内存与速度的权衡：基础版本使用布尔列表，内存占用尚可。对于极大的n（如 10^8），可以考虑使用bytearray或bitset（在C++中）来进一步压缩内存，这对缓存友好，能显著提升速度。

C++ 优化版本（使用 vector 特化）：

#include <iostream> #include <vector> using namespace std; vector<int> sieveEratosthenes(int n) { // vector<bool> 通常被特化以节省空间（每个元素占1 bit） vector<bool> is_prime(n, true); is_prime[0] = is_prime[1] = false; for (int i = 2; i * i < n; ++i) { // 用 i*i < n 代替 sqrt计算，更快 if (is_prime[i]) { // 注意：这里 j 可能会溢出 int，所以用 long long 或提前判断 for (int j = i * i; j < n; j += i) { is_prime[j] = false; } } } vector<int> primes; for (int i = 2; i < n; ++i) { if (is_prime[i]) primes.push_back(i); } return primes; }

注意：C++中vector<bool>的j += i操作，当n很大时，i*i可能超出int范围导致溢出，成为负数，从而引发段错误或死循环。这是埃氏筛一个经典的坑。安全的写法是内层循环变量j使用long long类型，或者增加判断if (i <= n / i)。

3.2 欧拉筛的实现与细节剖析

欧拉筛的逻辑稍复杂，但代码结构非常规整。

Python 实现：

def sieve_euler(n): """ 欧拉筛（线性筛），返回小于 n 的所有素数列表。 """ is_prime = [True] * n primes = [] # 用于存储已找到的素数 is_prime[0] = is_prime[1] = False for i in range(2, n): if is_prime[i]: primes.append(i) # i 是素数，加入列表 # 遍历已知素数 primes[j] for j in range(len(primes)): composite = i * primes[j] if composite >= n: # 超出范围，中断 break is_prime[composite] = False # 标记合数 # **核心：如果 i 能被当前素数整除，则跳出循环** if i % primes[j] == 0: break return primes # 示例 primes_linear = sieve_euler(100) print(primes_linear[:20])

C++ 实现：

#include <iostream> #include <vector> using namespace std; vector<int> sieveEuler(int n) { vector<bool> is_prime(n, true); vector<int> primes; is_prime[0] = is_prime[1] = false; for (int i = 2; i < n; ++i) { if (is_prime[i]) { primes.push_back(i); } // 用已知的素数 primes[j] 去筛 for (int j = 0; j < primes.size(); ++j) { long long composite = 1LL * i * primes[j]; // 防止溢出 if (composite >= n) break; is_prime[composite] = false; // 核心终止条件 if (i % primes[j] == 0) break; } } return primes; }

逐行解析与深度思考：

1. 外层循环for i in range(2, n)：注意，这里i是遍历每一个数，而不仅仅是素数。i扮演了两个角色：一是它本身可能是素数（if is_prime[i]分支），二是作为“乘数”与已知素数结合来生成新的合数。
2. if is_prime[i]: primes.append(i)：如果i没有被之前的素数筛掉，那么它一定是素数。这是因为欧拉筛的标记过程保证了所有合数都会被正确标记。
3. 内层循环for j in range(len(primes)):：用当前数i去乘以每一个已知的素数primes[j]，从而标记合数i * primes[j]。
4. if composite >= n: break：简单的边界检查，防止数组越界。
5. is_prime[composite] = false：执行标记。
6. if i % primes[j] == 0: break：灵魂所在。如前所述，这保证了composite只被其最小素因子primes[j]标记一次。理解这一点，就理解了欧拉筛。

一个具体的例子来验证：假设n=20，当前i=4，已知素数primes = [2, 3]。

• j=0:composite = 4*2=8，标记8，因为4%2==0，跳出循环。
• 为什么不让j=1继续？如果继续，composite = 4*3=12，会标记12。但12的最小素因子是2，它本应在i=6(6*2) 时被标记。现在标记就重复了。所以必须跳出。

4. 性能实测与场景选择指南

理论说了很多，是骡子是马，拉出来溜溜。我写了一个简单的测试脚本来对比两种筛法在不同数据规模下的表现。

import time import matplotlib.pyplot as plt def test_performance(): test_cases = [10**4, 10**5, 5*10**5, 10**6, 5*10**6] # 测试规模 times_eratosthenes = [] times_euler = [] for n in test_cases: # 测试埃氏筛 start = time.perf_counter() sieve_eratosthenes(n) end = time.perf_counter() times_eratosthenes.append(end - start) # 测试欧拉筛 start = time.perf_counter() sieve_euler(n) end = time.perf_counter() times_euler.append(end - start) print(f"n={n:8d}: 埃氏筛 {end-start:.4f}s, 欧拉筛 {times_euler[-1]:.4f}s") # 绘制对比图（此处省略绘图代码，实际可展示） # 通常结果：在 n 较小时（如<1e6），两者差距不大，埃氏筛可能因代码简单更快。 # 当 n 很大时（如>5e6），欧拉筛的线性优势开始明显体现。 if __name__ == "__main__": test_performance()

根据我的实测经验，选择建议如下：

个人心得：在绝大多数面试、笔试和日常开发中，埃氏筛完全足够。它的代码简单到几乎可以默写，不容易出错。除非题目明确要求线性复杂度，或者你在处理天文数字级别的数据（例如密码学相关应用），否则优先考虑埃氏筛。记住，“正确的简单算法”远胜于“复杂但可能写错的优化算法”。

5. 常见问题与排查技巧实录

在实际编码和调试中，你会遇到一些典型问题。这里我总结了一份“避坑指南”。

5.1 数组越界与溢出

这是最常遇到的运行时错误。

• 问题：在埃氏筛内层循环for j in range(i*i, n, i)中，当i很大时，i*i可能超过整数类型的最大值，导致溢出变成负数，进而使循环变量j初始值为负，或者导致条件判断失常。
• 现象：程序崩溃（段错误）或陷入死循环。
• 解决：
  1. 使用更大的数据类型：在 C++ 中，将内层循环的索引变量j声明为long long。
  2. 添加安全判断：在循环开始前判断if (i <= n / i)。因为只有当i*i < n时，内层循环才有意义。Python 的整数自动支持大数，但逻辑判断依然需要。

  // C++ 安全写法 for (int i = 2; i * i < n; ++i) { // 外层循环条件本身就隐含了 i*i < n if (is_prime[i]) { // 保险起见，内层循环用 long long for (long long j = (long long)i * i; j < n; j += i) { is_prime[j] = false; } } }

5.2 结果错误：漏筛或多筛

• 症状：程序能运行，但输出的素数列表明显不对（比如少了 2，或者包含了合数）。
• 排查步骤：
  1. 检查初始状态：确认is_prime[0]和is_prime[1]是否已设为False。这是新手最容易忘记的一步。
  2. 小规模测试：用n=30这样的小数字手动模拟或打印中间过程。打印出每次标记的合数，看是否符合预期。
  3. 重点检查欧拉筛的终止条件：确认if (i % primes[j] == 0) break;这行代码是否正确放置在内层循环中标记合数之后。如果放错了位置，逻辑就全乱了。
  4. 检查循环边界：埃氏筛的外层循环是for i in range(2, int(n**0.5)+1)，确保+1存在，因为range是右开区间。欧拉筛的外层循环是for i in range(2, n)。

5.3 性能未达预期

• 可能原因 1：使用了低效的数据结构。在 Python 中，对于超大n，使用list存储布尔值可能比bytearray或array('b')慢。在 C++ 中，vector<int>存储is_prime比vector<bool>或bitset慢且占用更多内存。
• 优化尝试：

  # Python 使用 bytearray 的埃氏筛 def sieve_eratosthenes_fast(n): is_prime = bytearray(b'\x01') * n is_prime[0] = is_prime[1] = 0 for i in range(2, int(n**0.5)+1): if is_prime[i]: is_prime[i*i:n:i] = b'\x00' * ((n - i*i - 1)//i + 1) # 切片赋值，更快 return [i for i in range(2, n) if is_prime[i]]

• 可能原因 2：编译器优化级别低（C++）。确保使用-O2或-O3优化标志进行编译。
• 可能原因 3：测量误差。在性能测试时，确保计时函数精度足够（如 Python 的time.perf_counter），并多次运行取平均值，避免单次运行的偶然性。

5.4 内存消耗过大

• 问题：当n为 10^8 时，一个布尔数组需要约 100MB 内存（假设每个布尔值占1字节）。这可能接近或超出某些环境的内存限制。
• 解决方案：
  1. 使用位级压缩：C++ 的std::bitset或std::vector<bool>（特化版）每个元素只占 1 bit。Python 可以使用bitarray第三方库。这样内存消耗可以降到原来的 1/8。
  2. 分段筛法：这是处理超大范围（如 10^12）素数的进阶技巧。核心思想是，内存中只维护一小段区间（如 10^6）的筛子，利用埃氏筛的原理分段处理。这需要更复杂的索引计算，但能突破内存限制。
  3. 只筛奇数：除了 2 以外，所有素数都是奇数。我们可以只创建一个大小为n/2的数组，用来表示奇数3, 5, 7, ...是否为素数。这样可以节省近一半内存，但索引映射会稍复杂（数字 -> 下标的转换）。

6. 进阶应用与扩展思考

掌握了基础筛法，我们可以看看它们能解决哪些更复杂的问题。

6.1 快速质因数分解

利用欧拉筛过程中得到的信息，我们可以在线性时间内预处理出每个数的最小质因子（LPF）。这为后续的质因数分解提供了 O(log n) 的强力工具。

def linear_sieve_with_lpf(n): """欧拉筛，同时记录每个数的最小质因子 (Least Prime Factor)""" lpf = [0] * (n + 1) # lpf[i] 表示 i 的最小质因子 primes = [] for i in range(2, n + 1): if lpf[i] == 0: # i 是素数 lpf[i] = i primes.append(i) for p in primes: if p > lpf[i] or i * p > n: break lpf[i * p] = p return primes, lpf def factorize(x, lpf): """利用 lpf 数组快速分解质因数""" factors = [] while x > 1: p = lpf[x] cnt = 0 while x % p == 0: x //= p cnt += 1 factors.append((p, cnt)) return factors # 预处理 primes, lpf = linear_sieve_with_lpf(10**6) # 快速查询 print(factorize(123456, lpf)) # 输出：[(2, 6), (3, 1), (643, 1)] 即 2^6 * 3 * 643

这个技巧在解决需要大量质因数分解的数学类竞赛题中非常有用。

6.2 筛法求欧拉函数/莫比乌斯函数

欧拉函数 φ(n) 表示小于等于 n 的正整数中与 n 互质的数的数目。利用欧拉筛的线性特性，我们可以在筛素数的同时，递推求出每个数的欧拉函数值。

def linear_sieve_phi(n): phi = list(range(n + 1)) # phi[i] 初始为 i primes = [] is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = False for i in range(2, n + 1): if is_prime[i]: primes.append(i) phi[i] = i - 1 # 素数的欧拉函数值为 i-1 for p in primes: if i * p > n: break is_prime[i * p] = False if i % p == 0: # i 和 p 不互质， i*p 与 i 的质因子相同 phi[i * p] = phi[i] * p break else: # i 和 p 互质 phi[i * p] = phi[i] * (p - 1) return phi phi = linear_sieve_phi(20) print(phi[1:]) # 输出 1 到 20 的欧拉函数值

类似地，也可以求莫比乌斯函数 μ(n)。这体现了筛法作为一种强大的数论预处理工具的通用性。

6.3 区间筛法

问题：求区间 [a, b) 内所有素数，其中 a 和 b 可能很大（比如 a=10^12, b=10^12+10^6），但区间长度 L = b-a 相对较小。 直接筛到 b 是不可能的。这时可以用埃氏筛的思想，只用一个大小为 L 的数组来筛这个区间。

思路：

1. 先用普通筛法求出所有小于等于 √b 的素数。
2. 对于每个求出的素数 p，在区间 [a, b) 内找到第一个能被 p 整除的数（可能是 p 本身，如果 p 在区间内），然后标记它的所有倍数。
3. 区间内未被标记的数就是素数。

def segment_sieve(a, b): """返回区间 [a, b) 内的所有素数""" if b <= 2: return [] # 第一步：筛出 [2, sqrt(b)) 内的素数 limit = int(b ** 0.5) + 1 is_prime_small = [True] * limit is_prime_small[0] = is_prime_small[1] = False for i in range(2, int(limit**0.5)+1): if is_prime_small[i]: for j in range(i*i, limit, i): is_prime_small[j] = False small_primes = [i for i in range(2, limit) if is_prime_small[i]] # 第二步：用 small_primes 去筛大区间 [a, b) is_prime_big = [True] * (b - a) if a == 0: is_prime_big[0] = False if a == 1: is_prime_big[0] = False # 如果区间包含1，需要特殊处理 for p in small_primes: # 找到大于等于 a 的第一个 p 的倍数 start = max(p * p, ((a + p - 1) // p) * p) # 标记区间内的倍数 for j in range(start, b, p): is_prime_big[j - a] = False # 收集结果 primes = [i + a for i, flag in enumerate(is_prime_big) if flag] return primes

区间筛法是处理“大海捞针”式素数问题的必备技能。

最后，关于选择埃氏筛还是欧拉筛，我的个人体会是：不要过早优化。除非性能分析明确告诉你这里成了瓶颈，否则优先使用更简单、更不易出错的埃氏筛。在算法竞赛中，10^6 以内的数据，两者时间差可能只有几毫秒，而调试一段复杂的欧拉筛代码花费的时间远不止这些。当你真正需要处理千万级甚至亿级的数据，并且对时间极其敏感时，欧拉筛的线性优势才会成为决定性的因素。把基础打牢，理解每一种算法背后的“为什么”，比死记硬背代码要重要得多。