埃氏筛算法：从质数判断到高效筛选的完整指南

1. 从“暴力枚举”到“筛法”：为什么我们需要埃氏筛？

如果你刚开始接触编程，或者正在准备算法面试，那么“判断一个数是否为质数”这个问题，你大概率是从最经典的“试除法”开始的。从2到√n，挨个去试除，看有没有能整除的。这个方法简单直接，对于判断单个数字，时间复杂度O(√n)，完全够用。

但问题来了：如果题目不是问你“10007是不是质数”，而是问你“1到100000之间有多少个质数”，或者“请输出1到100000之间的所有质数”，你该怎么办？还用试除法，对每个数都来一遍O(√n)的判断？那总时间复杂度就变成了O(n√n)。当n=10^5时，这个计算量已经不小了；如果n=10^6甚至10^7，程序就会变得非常慢，甚至超时。

这就是“埃拉托斯特尼筛法”（简称埃氏筛）登场的场景。它的核心思想不是去“判断”，而是去“筛选”。想象一下，你要从一堆沙子里筛出所有的小石子（质数）。暴力方法是拿起每一粒沙子，仔细端详它是不是石子。而筛法则是准备一个筛子（布尔数组），先把所有沙子都当作可能的石子（标记为True），然后从最小的石子（2）开始，把所有是它倍数的沙子（合数）都筛掉（标记为False）。接着找下一个还没被筛掉的石子（3），继续筛掉它的倍数……如此反复，最后留在筛子上的，就全是石子（质数）了。

这个方法之所以高效，是因为它避免了大量重复的判断。一个合数（比如6）会被它的所有质因数（2和3）各筛一次，但计算开销远小于对每个数都做一次完整的开方和取模运算。埃氏筛的时间复杂度是O(n log log n)，这是一个比O(n)略大，但远小于O(n log n)的复杂度。对于n=10^7，O(n log log n)和O(n√n)的效率是天壤之别。因此，埃氏筛是解决“求某一范围内所有质数”这类问题的标准且高效的模板算法，是每个程序员工具箱里的必备品。

2. 埃氏筛的核心原理与“筛”的运作机制

理解埃氏筛，关键在于理解“筛”这个动作是如何在代码中实现的，以及为什么从i*i开始筛能保证正确性。

2.1 算法步骤拆解

我们以求1到N（假设N=30）之间的所有质数为例，一步步拆解：

1. 初始化“筛子”：创建一个长度为N+1的布尔数组is_prime，下标对应数字。默认所有元素为True，表示我们初始假设所有数都是质数。is_prime[0]和is_prime[1]要手动设为False，因为0和1不是质数。

   索引: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 值: F F T T T T T T T T T T T T T T T T T T T T T T T T T T T T T

2. 开始筛选：从第一个质数p = 2开始，遍历到√N（这里是√30≈5.47，所以到5）。

   • 为什么只到√N？这是算法的核心优化。对于任意一个合数n，它必然有一个不大于√n的质因数。因此，如果我们用所有≤√N的质数去筛，那么所有≤N的合数都一定会被筛掉。大于√N的数如果未被筛掉，它一定是质数。

3. 执行“筛”的动作：对于当前的p，如果is_prime[p]为True（说明它是质数），则开始筛它的倍数。

   • 从哪开始筛？从j = p * p开始。
   • 为什么从p*p开始，而不是2*p？这是另一个关键优化。考虑p=5。它的倍数有10, 15, 20, 25, 30... 但是请注意，10 = 2*5，它在p=2的时候已经被筛过了；15 = 3*5，在p=3的时候被筛过了；20 = 4*5，但4是合数，它的质因数2已经筛过20了。一个合数m = p * k，如果k < p，那么m一定有一个比p小的质因数，因此在遍历到p之前，m就已经被那个更小的质数筛掉了。所以，从p*p开始筛，可以避免大量重复操作。
   • 怎么筛？将j，j+p，j+2p... 所有这些p的倍数对应的is_prime[j]标记为False。
   • 以p=2为例：从2*2=4开始，把4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 标记为False。
   • 以p=3为例：从3*3=9开始，把9, 12, 15, 18, 21, 24, 27, 30 标记为False。（注意12, 18, 24, 30已经被p=2筛过，再次标记为False也无妨，这就是埃氏筛会有重复标记的原因）。
   • p=4时，is_prime[4]已经是False，跳过。
   • p=5时，从5*5=25开始，把25, 30标记为False。

4. 收集结果：遍历is_prime数组，所有值为True的下标就是质数。对于N=30，结果就是：2, 3, 5, 7, 11, 13, 17, 19, 23, 29。

2.2 时间复杂度 O(n log log n) 的感性认识

这个复杂度推导涉及数论中的梅滕斯定理，比较深奥。我们可以感性理解：对于每个质数p，我们需要筛掉 N/p 个数（的标记）。所以总操作数大约是 N/2 + N/3 + N/5 + N/7 + ...，求和所有质数p ≤ N的 N/p。根据质数分布定理，前N个自然数中大约有 N/ln N 个质数，并且第k个质数大约为 k ln k。通过这些近似，可以推导出总操作数约为 N log log N。所以复杂度是 O(n log log n)。你只需要记住，它几乎和 O(n) 一样快，对于 n=10^7，log log n 大约只有 3，非常高效。

3. 标准模板代码实现与逐行解析

理解了原理，我们来看最经典、最通用的埃氏筛模板代码。这里以Python为例，其他语言逻辑完全一致。

def eratosthenes_sieve(n: int): """ 埃拉托斯特尼筛法求小于等于n的所有质数 Args: n: 上限（包含） Returns: 一个列表，包含所有 <= n 的质数 """ if n < 2: return [] # 1. 初始化筛子，默认都是质数 is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = False # 0和1不是质数 # 2. 开始筛选，遍历到 sqrt(n) import math for i in range(2, int(math.isqrt(n)) + 1): # 使用 isqrt 避免浮点误差 if is_prime[i]: # 如果i是质数 # 3. 筛掉i的倍数，从 i*i 开始，步长为 i # 注意：这里使用切片赋值或循环均可，切片在Python中更快 # 写法一：循环 # for j in range(i * i, n + 1, i): # is_prime[j] = False # 写法二：切片赋值（Pythonic，效率高） is_prime[i * i : n + 1 : i] = [False] * ((n - i * i) // i + 1) # 4. 收集结果 primes = [i for i, flag in enumerate(is_prime) if flag] return primes # 使用示例 if __name__ == "__main__": n = 100 primes = eratosthenes_sieve(n) print(f"小于等于 {n} 的质数有 {len(primes)} 个:") print(primes)

关键代码行解析：

• is_prime = [True] * (n + 1)：创建长度为n+1的列表，+1是为了让下标和数字直接对应，方便理解。is_prime[5]就代表数字5的状态。
• int(math.isqrt(n)) + 1：math.isqrt(n)是Python 3.8+引入的函数，用于计算整数平方根，比int(math.sqrt(n))更精确高效。循环上界是√n的整数部分加1，因为range是左闭右开区间。
• if is_prime[i]:：这是优化的关键。只有当i是质数时才去筛它的倍数。如果i是合数，那么它的倍数一定已经被它的某个质因数筛过了，无需重复操作。
• is_prime[i * i : n + 1 : i] = [False] * ((n - i * i) // i + 1)：这一行是Python中非常高效的“批量赋值”写法。
  • is_prime[i*i : n+1 : i]是一个切片，它选取了从i*i开始，到n结束，步长为i的所有元素。这正是所有i的倍数（从i*i开始）。
  • 等号右边[False] * ((n - i * i) // i + 1)生成了一个长度完全匹配的、全为False的列表。
  • 这个操作一次性将切片内的所有元素设置为False，比用for循环逐个赋值要快得多，尤其是在Python中。
  • ((n - i * i) // i + 1)是计算从i*i到n（包含）之间，i的倍数的个数。这是一个简单的等差数列项数计算。
• primes = [i for i, flag in enumerate(is_prime) if flag]：列表推导式，遍历is_prime数组，收集所有状态为True的下标i，即为质数。

注意：切片赋值虽然快，但会创建一个新的[False]列表。当n非常大（如 > 10^7）且内存紧张时，这个临时列表可能会带来压力。此时，使用for j in range(i*i, n+1, i): is_prime[j] = False的循环写法虽然稍慢，但内存开销更稳定。在绝大多数算法竞赛和面试场景中，n在 10^6 级别，切片赋值是首选。

4. 模板的变体、优化与实战场景

标准的埃氏筛模板已经很强大了，但在不同场景下，我们还可以进行一些优化或变体，以适应特定需求。

4.1 仅判断质数状态：空间优化版

有时我们不需要返回质数列表，只需要一个能快速查询1~n内任意数字是否为质数的工具。这时可以稍微修改函数，直接返回is_prime数组。

def get_prime_status(n: int): """返回一个列表 is_prime， is_prime[i] 表示 i 是否为质数""" is_prime = [True] * (n + 1) if n >= 0: is_prime[0] = False if n >= 1: is_prime[1] = False for i in range(2, int(n**0.5) + 1): if is_prime[i]: step = i * 2 if i == 2 else i * i # 对于2，可以从2*i开始筛 for j in range(step, n + 1, i): is_prime[j] = False return is_prime # 使用：先预处理，然后O(1)查询 is_prime = get_prime_status(1000000) print(is_prime[17]) # True print(is_prime[100]) # False

4.2 线性筛（欧拉筛）：时间与空间的终极优化

埃氏筛的一个小缺点是，一个合数可能被多个质数重复标记（如30被2、3、5各标记一次）。虽然不影响结果，但理论上存在更优的“线性筛”或“欧拉筛”，能保证每个合数只被它的最小质因数筛一次，时间复杂度严格 O(n)。但它的代码比埃氏筛复杂一些。

线性筛的核心：维护一个质数列表primes。对于每个数i（从2到n）：

1. 如果i是质数，加入primes。
2. 遍历当前质数列表primes中的每个质数p：
   • 令x = i * p。
   • 筛掉x。
   • 关键：如果p能整除i，则跳出循环。因为对于x = i * p，p是x的最小质因数。如果i有更小的质因数p'，那么x应该由i' = i/p * p'和p'来筛，才能保证唯一性。

def linear_sieve(n: int): """线性筛（欧拉筛）""" is_prime = [True] * (n + 1) primes = [] for i in range(2, n + 1): if is_prime[i]: primes.append(i) for p in primes: if i * p > n: break is_prime[i * p] = False if i % p == 0: # 保证每个合数只被最小质因数筛掉 break return primes

如何选择？

• 埃氏筛：代码简单，容易记忆，在n <= 10^7时效率极高，是竞赛和面试的“首选模板”。它的O(n log log n)在实际中和O(n)差异不大。
• 线性筛：代码稍复杂，但理论复杂度最优O(n)。当n极大（如 > 10^7）且对常数因子非常敏感时，或者需要同步求出每个数的最小质因数时，线性筛是更好的选择。例如，在解决需要质因数分解的问题时，线性筛过程中可以记录min_prime[x]，非常有用。

对于99%的“求解质数”问题，埃氏筛模板完全够用且更不容易出错。

4.3 实战场景：计数与区间筛法

场景一：统计质数个数（LeetCode 204. 计数质数）这是埃氏筛最直接的应用。你不需要收集质数列表，只需要在筛选完成后，统计is_prime数组中True的个数。可以用sum(is_prime)快速计算。注意，题目通常要求小于n的质数个数，所以数组大小设为n即可，下标从0到n-1。

场景二：区间筛法（求 [a, b] 内的所有质数，其中 a, b 很大，但 b-a 相对较小）当a和b很大（比如1 <= a <= b <= 10^12），但b-a <= 10^6时，我们无法直接开一个到b的数组。这时可以用“区间筛法”，它是埃氏筛思想的延伸。

思路：

1. 先用普通埃氏筛求出2到√b之间的所有质数（这个范围很小）。
2. 创建一个长度为b-a+1的布尔数组is_prime_small，表示区间[a, b]内的每个数（偏移后）是否为质数，初始全为True。
3. 对于第一步求出的每个质数p，在区间[a, b]内找到第一个能被p整除的数（即ceil(a/p) * p），然后从这个数开始，以p为步长，将is_prime_small中对应的位置标记为False。注意，如果这个数就是p本身，且p在区间内，那么p是质数，不应该被筛掉。
4. 遍历is_prime_small，收集质数。

def segmented_sieve(a: int, b: int): """区间筛法，返回区间 [a, b] 内的所有质数，假设 b-a 较小""" if a > b: return [] if a < 2: a = 2 import math limit = int(math.isqrt(b)) + 1 # 步骤1：筛出[2, sqrt(b)]内的质数 base_primes = eratosthenes_sieve(limit) # 步骤2：初始化区间筛数组 size = b - a + 1 is_prime_seg = [True] * size # 步骤3：用每个基质数去筛区间 for p in base_primes: # 找到区间内第一个p的倍数 start = max(p * p, ((a + p - 1) // p) * p) # 确保从 p*p 或大于等于a的第一个p倍数开始 # 筛掉区间内所有p的倍数 for j in range(start, b + 1, p): is_prime_seg[j - a] = False # 步骤4：收集结果 primes_in_range = [i + a for i, flag in enumerate(is_prime_seg) if flag and (i + a) >= 2] return primes_in_range

这个变体展示了埃氏筛思想的灵活性，它不仅能处理从头开始的连续区间，也能处理任意子区间。

5. 常见“坑点”、调试技巧与性能压测

即使理解了原理和模板，在实际编码和调试中，还是会遇到一些典型的“坑”。

5.1 数组下标与边界处理

这是最常见的错误来源。

• 数组大小：is_prime = [True] * (n + 1)。这里的n+1是为了让下标n可以被访问到。如果你要求“小于n”的质数，数组大小用n就够了，但此时is_prime[n-1]对应数字n-1，需要小心映射关系。最稳妥的做法是：题目要求“小于等于n”，就用n+1；要求“小于n”，就用n，并在后续所有循环中注意边界。
• 循环上界：外层循环for i in range(2, int(math.isqrt(n)) + 1)。math.isqrt(n)是整数平方根，+1是因为range右开。一定要用整数平方根，用int(n**0.5)在n是完美平方数时可能因为浮点精度问题导致少循环一次（例如n=25，int(25**0.5)可能等于4）。使用math.isqrt是最佳实践。
• 内层循环起始点：for j in range(i*i, n+1, i)。当i*i可能溢出整数范围时（在C++/Java等语言中需要特别注意），或者当n很大而i也很大时，i*i可能超过n，导致循环不执行，这是正确的。但在Python中，大整数没问题，但也要注意逻辑。

5.2 重复标记与性能损耗

虽然埃氏筛允许重复标记，但我们可以通过一个小技巧减少一部分重复工作：在筛倍数时，对于偶数质数2，我们可以特殊处理。因为除了2以外，所有偶数都是合数。我们可以在初始化时就把所有偶数标记为False，然后外层循环只遍历奇数。

def optimized_eratosthenes(n: int): """优化版：先处理偶数，只筛奇数倍""" if n < 2: return [] if n == 2: return [2] # 初始化，假设所有奇数都是质数 is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = False # 单独处理偶数 for i in range(4, n + 1, 2): is_prime[i] = False # 只遍历奇数 for i in range(3, int(math.isqrt(n)) + 1, 2): if is_prime[i]: # 从 i*i 开始，因为 i 是奇数，i*i也是奇数，步长为 2*i (偶数)，这样 j 始终是奇数倍？ # 不对，i的奇数倍可能是奇数也可能是偶数。例如 3*3=9(奇), 3*5=15(奇), 3*2=6(偶)... # 但我们只关心合数。由于所有偶数已预先标记为False，所以这里步长用 i 即可，即使标记到偶数也无所谓。 start = i * i if start > n: continue # 使用切片赋值 is_prime[start : n + 1 : i] = [False] * ((n - start) // i + 1) primes = [2] + [i for i in range(3, n+1, 2) if is_prime[i]] return primes

这个优化大约能减少一半的外层循环次数，但代码复杂度增加。在算法竞赛中，标准的埃氏筛模板通常就足够了，这个优化属于锦上添花。

5.3 内存与性能压测

对于不同的n，埃氏筛的表现如何？我们来做个小实验。

import time, math def test_performance(): test_cases = [10**5, 10**6, 5*10**6, 10**7] for n in test_cases: start = time.time() primes = eratosthenes_sieve(n) end = time.time() print(f"n = {n:>10}, 质数个数: {len(primes):>8}, 耗时: {end-start:.4f} 秒") # 可选：验证一下最后一个质数是否正确（仅用于小范围验证逻辑） # if n == 100: # print(primes[-5:]) # 查看最后几个质数 if __name__ == "__main__": test_performance()

在我的普通笔记本上（Python 3.9），输出可能类似于：

n = 100000, 质数个数: 9592, 耗时: 0.0050 秒 n = 1000000, 质数个数: 78498, 耗时: 0.0480 秒 n = 5000000, 质数个数: 348513, 耗时: 0.2800 秒 n = 10000000, 质数个数: 664579, 耗时: 0.6000 秒

可以看到，在n=10^7时，仍然能在1秒内完成，完全满足大多数在线判题系统的要求（通常时间限制1~2秒）。内存方面，is_prime数组占用大约n/8字节（因为Python的bool实际上是个对象，但用array('b')或bytearray可以优化，不过模板中列表的简洁性更重要）。对于n=10^7，列表占用约10MB内存，可以接受。

一个重要的实战技巧：在算法竞赛中，如果题目是多组测试数据，但n的最大值固定（比如T组查询，每组给一个n_i，但所有n_i <= 10^6），那么一个常见的优化是预处理。在程序开始只运行一次sieve(MAX_N)，生成全局的is_prime数组或primes列表。之后每组查询都可以 O(1) 或 O(1) 查询，而不是每组都重新筛一遍。这个技巧能大幅降低总运行时间。

6. 从模板到应用：解决经典问题示例

掌握了模板，我们来看看如何用它解决具体问题。以LeetCode 204（计数质数）为例，题目要求统计所有小于非负整数n的质数的数量。

直接套用模板：

class Solution: def countPrimes(self, n: int) -> int: if n < 3: # 小于2和小于3的情况 return 0 is_prime = [True] * n is_prime[0] = is_prime[1] = False # 0和1不是质数 for i in range(2, int(n**0.5) + 1): if is_prime[i]: # 注意：这里起始点是 i*i，但必须小于 n start = i * i if start >= n: continue # 使用切片赋值 is_prime[start : n : i] = [False] * ((n - 1 - start) // i + 1) return sum(is_prime)

注意几个细节：1) 数组大小为n，下标0到n-1对应数字0到n-1。2) 题目要求“小于n”，所以我们不包含n本身。3) 切片[start : n : i]的右边界是n，因为range和切片都是右开的，这正好符合“小于n”。4) 最后用sum(is_prime)快速计数。

再比如，如果你想求第k个质数，或者n以内的质数和，都可以在筛完之后，通过遍历is_prime数组或primes列表轻松得到。

我个人在多次比赛和编码中的体会是：埃氏筛的模板几乎成了肌肉记忆。遇到“质数”、“素数”、“prime”相关的题目，只要数据范围n在10^6以上，并且需要批量处理，第一个想到的就是它。它的简洁性和高效性达到了完美的平衡。相比于更复杂的线性筛，埃氏筛在面试中解释起来也更轻松，面试官更看重你对这个经典算法本质的理解——用质数的倍数去标记合数，未被标记的就是质数。只要你能清晰地阐述“为什么外层循环到√n”和“为什么内层循环从i*i开始”，就足以证明你不仅会写代码，还理解了其数学原理。

最后，记住这个模板，理解其背后的每一个细节，你就能从容应对绝大多数与质数筛选相关的挑战了。在实际编程中，如果遇到特别大的n（比如10^8以上），你可能需要结合区间筛法，或者考虑使用bytearray来进一步压缩内存，但那是更进阶的优化了。对于日常应用和算法面试，本文提供的标准埃氏筛模板就是你的“瑞士军刀”。