1. 从“暴力枚举”到“筛法”：为什么我们需要更聪明的算法？

在编程和算法学习的路上，判断一个数是不是质数，几乎是每个人都会遇到的第一个“坎”。新手最直观的想法，就是“暴力枚举”：对于一个给定的正整数 n，从 2 开始，一直试除到 n-1，如果中间有任何数能整除 n，那 n 就不是质数。这个方法简单直接，但效率极低。当 n 稍微大一点，比如到 10^6 这个量级，这种方法的计算量就变得难以接受。

更进一步的优化是，我们只需要试除到 √n 就可以了。因为如果 n 有一个大于 √n 的因子 a，那么它必然对应一个小于 √n 的因子 b（因为 a * b = n）。这个优化将时间复杂度从 O(n) 降到了 O(√n)，对于单个数的判断来说，已经是教科书级的优化了。但是，如果我们的问题变了：“请找出 1 到 1000 万之间的所有质数”。这时，即使对每个数都用 O(√n) 的方法判断，总计算量依然是天文数字。我们需要一种能“批量”生产质数的方法，而不是一个个地“检验”。

这就是“筛法”粉墨登场的时刻。筛法的核心思想不是“判断”，而是“排除”或“筛选”。它像一个精密的过滤器，通过一套既定的规则，主动地将合数（非质数）标记出来，最后剩下的就是质数。这种思路的转变，带来了效率的飞跃。今天我们要深入探讨的，就是筛法家族中最著名、也最基础的两个成员：埃拉托斯特尼筛法（简称埃式筛法）和欧拉筛法（也称线性筛法，或欧式筛法）。它们不仅仅是找出质数的工具，更是理解算法优化、空间换时间、以及数论基本性质的绝佳范例。无论你是正在准备算法面试，还是对程序效率有极致追求，吃透这两种筛法，都大有裨益。

2. 埃拉托斯特尼筛法：古老而经典的智慧

埃拉托斯特尼是古希腊的数学家，他在公元前就提出了这个算法，其简洁与高效令人惊叹。它的原理，可以用一个生活中的场景来类比：假设你有一张写满了从2开始连续整数的表格，你的目标是找出所有的质数。

2.1 核心原理与步骤拆解

埃式筛法的操作流程非常直观：

1. 建立初始列表：创建一个布尔数组isPrime[0...n]，初始时假设所有大于等于2的数都是质数（设为true）。
2. 从第一个质数开始：从p = 2开始（我们知道2是最小的质数）。
3. 标记倍数：如果isPrime[p]是true，那么对于所有k = p * 2, p * 3, p * 4, ...且k <= n的数，将isPrime[k]标记为false。因为这些数都是p的倍数，所以它们一定是合数。
4. 寻找下一个质数：找到下一个大于p且isPrime值仍为true的数，这个数就是下一个质数。重复步骤3。
5. 终止条件：当p * p > n时，就可以停止了。因为所有小于等于 n 的合数，其最小的质因子一定小于等于 √n。在标记完所有小于等于 √n 的质数的倍数后，剩下的未被标记的数就都是质数了。

让我们以找出 30 以内的质数为例，手动模拟这个过程：

• 初始列表（2到30都标记为质数）。
• p=2：标记 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 为合数。
• 下一个p=3（未被标记）：标记 9, 15, 21, 27 为合数。（注意：6, 12, 18等已经是合数，但重复标记不影响结果）。
• 下一个p=5（未被标记）：标记 25 为合数。
• 下一个p=7（未被标记）：7*7=49 > 30，停止。
• 此时，列表中未被标记的数：2, 3, 5, 7, 11, 13, 17, 19, 23, 29。这些就是30以内的所有质数。

2.2 代码实现与时间复杂度分析

基于上述原理，一个标准的埃式筛法实现如下（以Python为例）：

def eratosthenes_sieve(n): """ 返回小于等于n的所有质数列表。 """ if n < 2: return [] # 初始化布尔数组，索引代表数字，True表示是质数（假设） is_prime = [True] * (n + 1) 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... 已经被更小的质数标记过了 for j in range(i * i, n + 1, i): is_prime[j] = False # 收集所有质数 primes = [i for i in range(2, n + 1) if is_prime[i]] return primes # 示例：找出100以内的质数 print(eratosthenes_sieve(100))

时间复杂度分析：埃式筛法的时间复杂度是O(n log log n)。这个复杂度已经非常优秀，远优于对每个数单独进行 O(√n) 判断的 O(n√n)。log log n是一个增长极其缓慢的函数，即使 n 是 10^9，log log n也大约只有 5。因此，埃式筛法在实践中有很高的效率。

空间复杂度：需要 O(n) 的布尔数组来存储标记信息。

2.3 埃式筛法的优势与局限性

优势：

1. 原理简单：逻辑清晰，极易理解和实现，是学习筛法的完美起点。
2. 效率足够：对于绝大多数需要一次性预处理质数表的场景（如竞赛编程中 n ≤ 10^7），O(n log log n) 的复杂度完全够用，且常数很小，运行速度快。
3. 易于优化：存在一些经典的优化技巧，如只筛选奇数、使用位图（bitset）压缩空间等，能进一步提升性能。

局限性（核心缺陷）：

1. 重复标记：这是埃式筛法最根本的效率瓶颈。一个合数可能被多个质因子重复标记。例如，合数 30 = 2 * 15 = 3 * 10 = 5 * 6，它会被质数2、3、5各标记一次。当 n 很大时，这种重复劳动会累积成可观的开销。
2. 非线性时间复杂度：虽然 O(n log log n) 很好，但理论上存在更优的 O(n) 算法。

注意：在代码实现中，内层循环从i * i开始是一个关键优化。为什么不是从2 * i开始？因为对于质数i，2*i,3*i, ...,(i-1)*i这些数，它们的最小质因子一定小于i，所以在之前遍历到更小的质数时，就已经被标记过了。从i*i开始可以避免这部分重复工作。

3. 欧拉筛法：追求极致的线性效率

为了克服埃式筛法“重复标记”的缺陷，欧拉筛法（线性筛法）应运而生。它的核心目标是：确保每个合数只被其最小的质因子标记一次，从而达到理论上的 O(n) 时间复杂度。

3.1 算法原理：如何保证只标记一次？

欧拉筛法同样维护一个质数表primes和一个状态数组is_prime。但其运行逻辑更为精巧：

1. 外层遍历所有数：从 2 到 n，遍历每一个整数i。
2. 维护质数表：如果当前数i是质数（is_prime[i]为真），则将其加入质数表primes。
3. 内层遍历已知质数：无论i是否是质数，都遍历当前已找到的质数表primes中的每个质数p。
4. 标记合数与关键中断：
   • 计算合数n = i * p。
   • 如果n超过上限，则跳出内层循环。
   • 标记is_prime[n] = False。
   • 最关键的一步：如果i能被当前质数p整除（即i % p == 0），则在标记完n = i * p后，立即跳出内层循环。

为什么这个中断条件如此重要？这正是保证每个合数只被标记一次的灵魂所在。

让我们来推演一下：假设我们要标记合数x。设x的最小质因子是p_min。那么x一定可以表示为x = i * p_min，其中i = x / p_min。 在欧拉筛法的运行过程中，当外层循环i取到x / p_min这个值时，内层循环会遍历质数表。当遍历到质数p_min时，我们会标记x = i * p_min。

• 如果此时i已经包含了质因子p_min（即i % p_min == 0），那么对于后续比p_min更大的质数p‘，如果我们继续标记i * p’，这个合数的最小质因子就不是p‘了，而是p_min。这会导致重复标记。因此必须中断。
• 如果i不包含质因子p_min，那么p_min就是x的最小质因子，这次标记是唯一且正确的。

通过这个机制，每个合数x都会在其最小质因子p_min与对应的i = x / p_min相遇时，被标记一次，且仅此一次。

3.2 代码实现与逐行解析

def euler_sieve(n): """ 返回小于等于n的所有质数列表（欧拉筛法/线性筛法）。 """ is_prime = [True] * (n + 1) primes = [] # 用于存储找到的质数 for i in range(2, n + 1): if is_prime[i]: primes.append(i) # 步骤1：i是质数，加入列表 # 步骤2：遍历当前已知的质数 for p in primes: composite = i * p if composite > n: # 超过范围，跳出 break is_prime[composite] = False # 标记合数 if i % p == 0: # ***核心中断条件*** break return primes # 示例 print(euler_sieve(100))

让我们跟踪一段执行过程，以理解其精妙。假设n=20。

• i=2: 是质数，primes=[2]。内层循环：p=2,composite=4<=20，标记4为合数。判断2 % 2 == 0，中断。
• i=3: 是质数，primes=[2,3]。内层循环：
  • p=2:composite=6，标记6。3 % 2 != 0，继续。
  • p=3:composite=9，标记9。3 % 3 == 0，中断。
• i=4: 不是质数（已标记）。primes=[2,3]。内层循环：
  • p=2:composite=8，标记8。4 % 2 == 0，中断。（注意，没有用p=3去标记12，因为12的最小质因子是2，它会在i=6时被p=2标记）
• i=5: 是质数，primes=[2,3,5]。内层循环：
  • p=2:composite=10，标记10。5 % 2 !=0，继续。
  • p=3:composite=15，标记15。5 % 3 !=0，继续。
  • p=5:composite=25>20，跳出循环。
• i=6: 不是质数。primes=[2,3,5]。内层循环：
  • p=2:composite=12，标记12。6 % 2 == 0，中断。（没有标记18，因为18的最小质因子是2，将在i=9时被p=2标记？这里需要仔细分析：实际上，18 = 9 * 2，当i=9时，p=2会标记18。因为9的最小质因子是3，但p=2小于3，所以i=9时，p=2仍会参与循环并标记18，然后遇到9 % 2 != 0继续，再用p=3标记27时中断。所以18被正确标记了一次。）

通过这个过程可以看到，每个合数（如12）都只被标记了一次。

3.3 欧拉筛法的优势与代价

优势：

1. 理论复杂度最优：严格 O(n) 的时间复杂度。在处理极大范围的质数筛选时（例如 n > 10^7），其优势开始显现。
2. 无重复计算：每个合数只被访问一次，消除了埃式筛法的冗余操作。

代价与注意事项：

1. 逻辑复杂度高：理解其正确性，特别是中断条件，比埃式筛法困难得多。
2. 常数可能更大：虽然理论复杂度低，但由于其内层循环的逻辑判断（求模运算i % p）相对昂贵，在n不是特别大（比如 n < 10^7）时，其实际运行速度可能不如高度优化过的埃式筛法（如仅处理奇数的位运算版）。
3. 对缓存不友好：内层循环需要跳跃式访问primes列表和is_prime数组，可能不如埃式筛法的连续内存访问模式高效。

实操心得：在算法竞赛或日常编程中，如果题目给定的n在 10^7 量级以下，优先使用埃式筛法。它代码简单，不易出错，且经过位图优化后速度飞快。只有当题目明确要求 O(n) 复杂度，或者n的范围极大（如 10^8），你才需要考虑实现欧拉筛法。在面试中，能清晰阐述欧拉筛法的原理，通常比写出无 bug 的代码更能体现你的理解深度。

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

理论分析很重要，但实际运行速度才是最终标准。我们设计一个简单的测试来对比两种算法。

import time def test_performance(n): print(f"测试范围: 1 - {n}") start = time.time() primes_eratosthenes = eratosthenes_sieve(n) time_eratosthenes = time.time() - start print(f"埃式筛法 耗时: {time_eratosthenes:.4f} 秒，找到 {len(primes_eratosthenes)} 个质数") start = time.time() primes_euler = euler_sieve(n) time_euler = time.time() - start print(f"欧拉筛法 耗时: {time_euler:.4f} 秒，找到 {len(primes_euler)} 个质数") # 验证结果一致性 assert primes_eratosthenes == primes_euler, “结果不一致！” print("结果验证: 一致") print("-" * 40) if __name__ == "__main__": test_performance(10**6) # 100万 test_performance(5*10**6) # 500万 test_performance(10**7) # 1000万

在我的开发环境（普通笔记本）下，可能得到类似如下的结果（具体时间因机器而异）：

测试范围: 1 - 1000000 埃式筛法 耗时: 0.0352 秒，找到 78498 个质数 欧拉筛法 耗时: 0.0481 秒，找到 78498 个质数 结果验证: 一致 ---------------------------------------- 测试范围: 1 - 5000000 埃式筛法 耗时: 0.2153 秒，找到 348513 个质数 欧拉筛法 耗时: 0.2810 秒，找到 348513 个质数 结果验证: 一致 ---------------------------------------- 测试范围: 1 - 10000000 埃式筛法 耗时: 0.4521 秒，找到 664579 个质数 欧拉筛法 耗时: 0.5785 秒，找到 664579 个质数 结果验证: 一致

结果分析：在千万量级以下，基础的埃式筛法实现反而比欧拉筛法更快。这是因为欧拉筛法每次迭代中的求模运算i % p带来了不小的常数开销。而埃式筛法的内层循环是简单的加法j += i，现代CPU对此优化得非常好。

那么欧拉筛法的优势在哪里？

1. 复杂度上限：当n继续增大到亿级甚至十亿级时，O(n) 和 O(n log log n) 的差距会逐渐体现出来。欧拉筛法的增长更线性。
2. 衍生应用：欧拉筛法的框架极其强大。它不仅能筛质数，还能在筛的过程中，以 O(n) 的复杂度同步计算出许多数论函数，例如：
   • 每个数的最小质因子。
   • 欧拉函数 φ(n)。
   • 莫比乌斯函数 μ(n)。
   • 除数函数等。 这是埃式筛法难以高效完成的。例如，要计算1到n每个数的欧拉函数，使用欧拉筛法可以在 O(n) 内完成，而其他方法则复杂得多。

4.1 如何选择？决策流程图

面对一个问题，你可以遵循以下思路选择：

是否需要一次性筛选出 1~N 的所有质数？ | |-- 否 --> 使用单个数的判定算法（试除法，Miller-Rabin等）。 | |-- 是 | |-- N <= 10^7，且只需质数列表？ | | | |-- 是 --> 使用 **优化后的埃式筛法**（推荐：仅奇数+位图）。 | | | |-- 否 --> 除了质数，是否还需要每个数的最小质因子、欧拉函数等附加信息？ | | | |-- 是 --> 使用 **欧拉筛法**。 | | | |-- 否 --> 继续判断。 | |-- N > 10^7，或对时间复杂度有严格O(n)要求？ | |-- 是 --> 使用 **欧拉筛法**。 | |-- 否 --> 仍可优先尝试优化版埃式筛法。

4.2 埃式筛法的经典优化技巧

如果你选择了埃式筛法，这些优化可以让你如虎添翼：

1. 仅处理奇数：除了2以外，所有偶数都不是质数。我们可以只初始化一个表示奇数的布尔数组，大小减半，内存和计算量都减半。
2. 使用位图（Bitset）：用 Python 的int或bytearray，或者 C++ 的std::bitset，Java 的BitSet来存储标记。一个比特位代表一个数的状态，能将空间消耗降低到原来的 1/8 甚至更多。
3. 分段筛选：当n极大，无法一次性分配O(n)内存时，可以将区间分段，每次只筛一段。这需要更复杂的边界处理，但能突破内存限制。

这里给出一个 Python 的“仅奇数”优化版埃式筛法示例：

def optimized_eratosthenes_sieve(n): """优化版埃式筛法：仅处理奇数，使用半长数组。""" if n < 2: return [] if n == 2: return [2] # is_prime[i] 代表数字 (2*i + 3) 是否为质数 limit = (n - 1) // 2 is_prime = [True] * (limit + 1) primes = [2] # 先把2加入质数表 # 只遍历奇数 for i in range(limit + 1): if is_prime[i]: p = 2 * i + 3 # 当前代表的实际质数 primes.append(p) # 从 p*p 开始标记，注意步长为 2*p (因为只关心奇数倍) start = (p * p - 3) // 2 if start <= limit: for j in range(start, limit + 1, p): is_prime[j] = False return primes

这个版本在处理大数时，速度和内存表现都远优于基础版本。

5. 从筛法到更广阔的数论世界

理解埃式筛法和欧拉筛法，不仅仅是掌握了两个找质数的工具。它们背后蕴含的思想，是打开数论和算法优化大门的一把钥匙。

埃式筛法教会我们“以空间换时间”和“批量处理”的思想。通过预分配一个状态数组，我们避免了大量重复的、独立的计算。这种预处理思想在动态规划、前缀和、树状数组等算法中随处可见。

欧拉筛法则更深入地揭示了数的本质结构——每个合数都有唯一的最小质因子分解。它通过精巧的循环控制，确保了每个数只被其“最小质因子”访问一次。这种“每个元素只处理一次”的思想，是很多线性时间算法的核心，比如拓扑排序、KMP算法的一部分。

在实际应用中，质数筛选是许多高级算法的基础模块：

• 质因数分解：先筛出一定范围内的质数，可以快速对一个数进行分解。
• RSA加密算法：需要生成大质数，高效的质数测试和筛选是关键步骤。
• 解决与公约数、公倍数相关的问题：常常需要利用质数分布的性质。
• 各类数论函数的前缀和计算：如欧拉函数前缀和、莫比乌斯函数前缀和，其高效计算都离不开线性筛。

最后再分享一个小技巧：在面试或竞赛中，如果被问到质数相关问题，可以先从最基础的试除法讲起，然后自然引出其效率瓶颈，再提出埃式筛法作为优化，并分析其复杂度。如果面试官追问，再深入探讨欧拉筛法的原理和优势。这样的回答层次分明，能很好地展示你的知识体系。自己实现时，如果时间允许，可以先写一个清晰的埃式筛法，并提及“还有更优的线性筛法，但此处出于时间考虑使用埃式筛”。这比直接写一个可能有 bug 的欧拉筛法要稳妥得多。毕竟，在绝大多数场景下，正确且高效的埃式筛法已经足够出色。