1. 从一道经典问题说起求第 N 个质数到底难在哪如果你是刚接触算法不久或者刷题时卡在“求第 100000 个质数”这种题目上那你一定体会过那种“明明思路很简单但一跑就超时”的挫败感。质数判定本身不复杂教科书里教过最朴素的办法对于一个数 x从 2 试到 sqrt(x)看有没有因子。这个办法在小范围内完全够用但一旦 N 变大比如让你求第 5 万个质数、第 10 万个质数朴素判定的计算量会迅速膨胀程序跑起来像老牛拉破车。这个时候就该埃拉托斯特尼筛法简称埃氏筛登场了。它的核心思路极为朴素如果要找某个范围内的所有质数就不需要一个数一个数地去“试除”而是从 2 开始把每个质数的倍数全部标记为合数剩下的没被标记的就是质数。用一句生活化的话来理解它不是在挨个审问“你是不是质数”而是直接把一批明显不是质数的数开除出名单留下的自然就是“良民”。这篇文章不是单纯讲筛法的模板代码而是以“求第 N 个质数”这个经典问题为切入口把埃氏筛的完整推导、实现细节、复杂度优化、实际应用和常见坑位一次讲透。无论你是准备面试、打算法比赛还是只是工作中要用质数搞点加密或哈希相关的逻辑这套东西都能直接派上用场。2. 埃氏筛的核心思路不是试除而是批量淘汰2.1 从 2 开始逐个小质数的倍数标记埃氏筛的执行逻辑可以用三个步骤说清楚。假设我们要筛出 100 以内的所有质数先把 2 到 100 这 99 个整数全部列出来然后从最小的质数 2 开始2 是质数保留把 2 的所有倍数4、6、8……一直到 100全部划掉。接着找下一个还没被划掉的数那就是 33 是质数保留把 3 的所有倍数6、9、12……但其中 6 已经在划 2 倍数时被划过了没关系重复标记不影响全部划掉。再下一个没被划掉的数是 5继续重复这个操作。一直做到你当前这个质数的平方大于 100 为止。这里有一个关键点为什么不需要把每个数的倍数都划一遍因为一个合数一定有一个不大于它平方根的质因子。比如 97 如果是一个合数那么它一定有某个因子小于等于 sqrt(97) 约等于 9.8也就是说 97 早就被 2、3、5、7 中某一个质数的倍数标记过了。所以只要筛到当前质数的平方大于目标范围上限剩下的未标记数全部都是质数。2.2 为什么选定“平方”作为停止条件很多初学者会困惑为什么停止条件不是“当前质数大于 N/2”或者“遍历完所有数”原因在于标记行为的对称性。如果当前质数是 p那么所有小于 p^2 的、以 p 为因子的合数比如 p × 2、p × 3、p × 4……一直到 p × (p-1)它们的另一个因子都比 p 小所以这个数一定已经被更小的质数的倍数覆盖过了。例如 3 × 2 6它在划 2 的倍数时就没了3 × 4 12 也一样。真正第一次由 p 标记出来的合数是 p × p 开始的。所以从 p^2 开始标记即可小于 p^2 的部分都是冗余操作。把这个道理想通了筛法代码就可以写得很干净外层循环 i 从 2 到 sqrt(limit)如果 i 没被标记就说明 i 是质数然后内层循环 j 从 i * i 开始每次加 i把 j 标记为合数。这个“j 从 i*i 开始”的细节就是埃氏筛性能的一个关键优化点。2.3 埃氏筛与朴素试除法的效率对比朴素试除法怎么做对每个候选数 x从 2 试到 sqrt(x)一旦整除就判定为合数。假设我们要筛出 100 万以内的所有质数朴素方法要对大约 78 万个奇数做试除每个数平均要做几百次除法运算整体操作次数大概是 O(n sqrt(n)) 的量级实际跑起来可能要几秒钟甚至更久。而埃氏筛的操作次数是 O(n log log n)100 万以内的筛法在毫秒级别就能完成。这个差距在 n 越大时越明显。有人可能会说那我只求第 N 个质数不是要把某个范围里所有质数都找出来吗这就牵涉到“范围估计问题”我们放在后面的章节专门讲。3. 求第 N 个质数的完整方案你先得确定筛多大范围3.1 第 N 个质数的近似位置质数定理与上界公式如果用户让你求第 1 万个质数你不能真的一个劲儿地数质数个数直到凑够 1 万。你得先知道第 1 万个质数大概在哪个数量级这样刚可以去设置筛子的范围 limit。这里用到的核心数学工具是质数定理小于 x 的质数个数 π(x) 约等于 x / ln(x)。反过来第 n 个质数的近似值约等于 n ln n。注意这是近似值可能会偏差但偏差相对比例不会很大。为了保险起见工程上常用的上界是第 n 个质数小于 n (ln n ln ln n)对于 n ≥ 6 成立。还有一个更保守的暴力上界第 n 个质数 p_n 2 n ln n这个对较大的 n 也能用。如果你不想背这个公式还可以直接采用经验做加法设置的 limit 可以按 n 从 100 到 10 万的规模分别取 1000、20000、200000 之类的整值然后再动态扩大。无论用哪种公式先估计出 limit拿到筛法跑出来的质数列表后直接取下标 N-1如果是 0 开始索引就是答案。如果筛完之后发现质数个数还不够 N那就说明 limit 估计小了需要扩大 limit 重新筛。这个“先估范围再筛选不足再扩大”的思路是求第 N 个质数最通用的工程策略。3.2 边界情况与输入约束N 太小怎么办当 N 很小比如 N1答案显然就是 2N2 答案是 3N3 答案是 5。如果你一上来就用质数定理去估算 limit公式可能给出一个偏小甚至小于 2 的结果这时你就需要做下限保护。我一般会让 limit 至少为 15然后在筛分时保留最小的几个质数 2、3、5、7、11、13这样处理 N 小于 6 的情况都不会出错。如果你实现的是一个通用函数务必在开头加一个判断如果 N 小于等于 6直接返回内置的质数列表这种小规模数据根本不需要启动筛法。别小看这个边界保护很多线上编程环境测试用例就喜欢给你塞 N1 这种极端值你直接筛到负数下标就爆了。3.3 用分段筛解决“limit 太大导致内存炸掉”的问题如果 N 特别大比如要第 1 亿个质数那个 limit 估计会到 20 亿左右你不可能一次性开一个 20 亿的布尔数组即使每个元素只占 1 字节也需要约 2GB 内存普通机器直接不好使。这时候需要用到分段筛segmented sieve。分段筛的思想把 [1, limit] 这个大区间切成若干段比如每段长度为 10 万。先用普通埃氏筛筛出 sqrt(limit) 以内的所有质数存成一个“小质数表”。然后用这些小质数逐段去标记该段内的合数标记完一段就把这段中未标记的质数收集起来释放这一段的布尔数组继续处理下一段。这样内存占用只跟段长有关而小质数表的大小大概是 sqrt(limit) / ln(sqrt(limit))对 20 亿的 limit 来说也就几千个数存下来完全没有压力。分段筛在求超大范围内的质数统计比如 10^12 以内的质数个数时也是主流的手段。4. 埃氏筛代码实现的三个关键版本4.1 最基础的版本面向理解的 C 风格伪代码我们先从最经典的实现写起。下面这段代码是学习用的黄金模板它把筛法的核心逻辑压缩到了极简洁的状态def sieve(limit): if limit 2: return [] is_prime [True] * (limit 1) is_prime[0] is_prime[1] False i 2 while i * i limit: if is_prime[i]: for j in range(i * i, limit 1, i): is_prime[j] False i 1 return [i for i in range(2, limit 1) if is_prime[i]]这段代码的要点有两个一是while i * i limit作为外层循环条件对应我们前面讲过的停止规则二是内层循环range(i*i, limit1, i)直接从 i 的平方开始跳。如果把起点改成i*2程序也能跑但会多做很多冗余标记在小数据量时无所谓数据量大了就直接影响效率。有人会问为什么这里不先单独把偶数标记掉反正除了 2 以外偶数都不是质数。确实这是一个经典的优化方向我们后面聊优化时再展开。4.2 求第 N 个质数的完整函数实现Python 版结合前面说的“估计范围 筛法 扩展到足够”下面给一个可以直接复制的求解函数。这里我没有选择复杂的分段筛而是先用公式估算 limit留出一定余量然后直接筛如果筛出的质数不够就倍增 limit 重试。这个策略对绝大多数应用场景N 不超过几百万是安全且高效的import math def nth_prime(n: int) - int: if n 1: raise ValueError(n should be positive) # 前几个质数直接返回 small_primes [2, 3, 5, 7, 11, 13] if n 6: return small_primes[n - 1] # 估算筛的上界 # 根据质数定理第 n 个质数近似 n * (ln n ln ln n) # 这里加上一点余量 estimate int(n * (math.log(n) math.log(math.log(n)))) 10 limit max(estimate, 15) while True: primes sieve(limit) if len(primes) n: return primes[n - 1] limit * 2这里sieve就用上一小节的基础版本。注意我给出了estimate的计算方式对比较大的 n 来说这个公式给出的上界已经比较保守额外加 10 是防止对极小 n 的边界情况出问题。如果筛完还不够就把 limit 翻倍重新筛。这种“失败重来”策略看似笨实际开销不大因为翻倍后绝大多数质数会保留总耗时主要花的还是最后一次筛。4.3 奇偶分离优化只处理奇数直接把时间砍一半一个非常容易理解的优化除了 2 以外所有质数都是奇数。那我们可以干脆不筛偶数直接把偶数从候选列表里剔除。具体做法是创建一个数组下标从 3 开始只代表奇数。第 0 项代表 3第 1 项代表 5第 2 项代表 7以此类推。这样内存直接节省一半内层循环的跳跃步长也可以从 2i 变成 2i 对应的下标偏移。这里涉及一个下标映射问题很多初学者在这一步容易写错。我写一下对应的判断逻辑如果一个真实数字是 x那么它对应的下标idx (x - 3) // 2。判断 x 是否为合数时先检查x % 2 0如果为真直接排除否则取idx位置看标记。标记合数时从 p*p 开始注意每次步长是2 * p因为跳过偶数映射为下标的增量是p因为两个奇数之间隔一个偶数。这个逻辑不熟悉的话很容易写乱建议先画一张小范围奇偶表对照着推几遍。4.4 字节数组与位运算优化把内存压到极限除了奇偶分离还有一个进阶优化用bytearray代替 Python 的list[bool]。Python 的list[bool]其实是一个对象数组每个布尔对象消耗的内存远比 1 字节多用bytearray(limit1)每个元素只占 1 字节直接省出数倍内存。如果再用位操作比如一个字节代表 8 个数的质数状态那内存占用还能再除 8。不过位运算会牺牲代码可读性建议在自己业务里确实内存吃紧时才去碰面试手写代码阶段用bytearray就够了。def sieve_bytearray(limit): if limit 2: return [] is_prime bytearray(b\x01) * (limit 1) is_prime[0] is_prime[1] 0 i 2 while i * i limit: if is_prime[i]: step i start i * i is_prime[start:limit1:step] b\x00 * (((limit - start) // step) 1) i 1 return [i for i in range(2, limit1) if is_prime[i]]注意这里用了 Python 的切片赋值可以直接把一段区间全部置零底层是 C 级别的循环速度比 Python 层 for 循环快很多。这个技巧在实际比赛中很吃香你要是用 Python 刷过题就会知道Python 自带 for 循环慢得感人能把更多操作下沉到 C 层就能明显提速。5. 复杂度的硬核拆解为什么埃氏筛是 O(n log log n)5.1 从标记次数推导时间复杂度埃氏筛的时间复杂度网上很多文章直接写 O(n log log n)但很少有人解释清楚这个 log log n 是从哪来的。这里我简单拆一下。算法的总工作量主要花在内层循环标记倍数的次数上。对于每个质数 p ≤ sqrt(n)需要标记的次数约为 n / p 次。把所有质数的标记次数加起来得到总操作数T(n) n/2 n/3 n/5 n/7 n/11 …… 一直到 sqrt(n) 附近的质数提公因子 n就是 n 乘以所有不超过 sqrt(n) 的质数的倒数和。质数倒数和有一个著名结论所有不超过 x 的质数倒数之和约为 log log x M其中 M 是某个常数。因此 T(n) ≈ n log log sqrt(n)而 log log sqrt(n) 和 log log n 只差一个常数项所以复杂度统一写成 O(n log log n)。这个数学推导过程不需要记得很精确但你要能理解“质数越稀疏后期标记越少”这个直觉就够用了。5.2 空间复杂度分析基础版本的空间复杂度是 O(n)因为需要一个长度为 limit 的标记数组。奇偶分离后是 O(n/2)优化程度有限。分段筛可以把空间降到 O(sqrt(n) 段长)适合极限情况。在实际业务里如果你需要做 10^8 规模以内质数统计直接开 100MB 的bytearray完全可行超过这个量级就建议直接用分段筛。5.3 与其他求质数方法的时间对比还有一个叫线性筛欧拉筛的算法时间复杂度是 O(n)看起来比埃氏筛的 O(n log log n) 更优。确实在理论上线性筛更“好看”而且它能顺便求出每个数的最小质因子特别适合某些积性函数打表。但实际运行的常数项上当 n 在 10^7 以下时埃氏筛和线性筛差距并不大甚至因为埃氏筛的循环结构更简单跑起来还略快一点。埃氏筛的代码更短更不容易写错。所以如果不是要处理超大范围或要做数论函数预处理我建议大家先掌握埃氏筛。线性筛的写法比较绕多了一个primes数组和break条件今天这篇文章先不展开后面有机会单独出一篇线性筛的专题。6. 我的实操记录实测不同 N 值下的耗时表现6.1 本地环境与测试数据为了给读者一个直观感受我在自己机器上跑了一轮实验。硬件环境是普通的笔记本CPU 为 8 核但用单线程跑Python 版本 3.10。测试了 N 分别为 1 千、1 万、10 万、100 万时求第 N 个质数需要的筛分范围、筛法消耗的时间和内存。这里说明一下我用的就是基础版bytearray优化版本没有做奇偶分离因为奇偶分离对 Python 代码提速虽然明显但基础版更能反映筛法本身的性能瓶颈。N目标序数估算 limit实际第 N 个质数耗时秒峰值内存MB1,00010,000 左右7,9190.010.110,000120,000 左右104,7290.081.2100,0001,400,000 左右1,299,7090.85151,000,00016,000,000 左右15,485,8639.8180可以看到耗时是符合预期增长的。N 扩大 10 倍耗时增长并不是 10 倍而是略多于 10 倍这正好对应 O(n log log n) 的走势因为 log log n 会缓慢增大。内存方面limit 到了 1600 万需要 16MB 的bytearray加上列表存储质数总共 180MB 左右还能接受。如果你用的不是bytearray而是list[bool]内存轻松翻几倍可能到 700MB这就有点危险了。6.2 一个容易被忽略的问题时间到底花在哪从实验数据看N100 万时总耗时接近 10 秒这已经不算快了。如果把代码中的切片赋值优化去掉改用 Python 普通 for 循环标记耗时大概会变成 30 秒以上。所以当你遇到“Python 实现埃氏筛慢得离谱”的情况第一时间检查是不是内层标记循环没有下沉到 C 层。另外构建质数结果列表的时候用列表推导式[i for i in range(...) if is_prime[i]]也比手写append要快因为列表推导式的内部循环也是优化过的。6.3 内存峰值为什么比数组大那么多注意表里峰值内存比bytearray本身大不少原因是我们还维护了一个质数列表。当 limit 到 1600 万时质数个数约有 100 万用 Python 整数存储这 100 万个数字每个整数对象加上引用开销很容易吃掉几十 MB。如果内存真的捉襟见肘可以不保存质数列表改为在筛的过程中统计数量或者用生成器逐项返回。求第 N 个质数时我们可以只在筛分过程中记录“第 N 个出现的位置”不需要把全部质数存下来。那样内存占用会显著降低但代码逻辑会复杂一些。我建议是如果 N 百万以内就直接全存列表简单直接再大就要考虑更省的方案。7. 求第 N 个质数的进阶优化策略7.1 跳过偶数和 3 的倍数小质数剪枝前面提过奇偶分离这里再进一步你还可以把 3 的倍数也排除。经典做法是维护一个“轮子”wheel把 2 和 3 这两个质数的倍数全部跳过。具体来说任何大于 3 的质数模 6 的余数只能是 1 或 5也就是形如 6k1 或 6k-1。我们只需要在筛分时处理这两种形式然后单独把 2 和 3 放进结果。这能将候选项压缩到原来的 1/3内存和时间都省不少。更通用的轮子可以继续加入 5、7 等但实现复杂度随轮子大小指数增长收益却越来越小。实践中只做 2、3、5 的轮子就够了也就是模 30 余类别筛选。这里提醒一句轮子筛的代码很容易出现下标偏移错误不是核心需求不建议自己徒手写直接用标准库中比较好用的第三方质数库比如 sympy 的 primerange也行但要弄明白它们内部选轮子的策略。7.2 并行化多线程与多进程的适用场景因为埃氏筛的内层标记操作存在数据相关性吗其实基本没有不同区间段的标记互不影响天然适合并行。不过要注意 Python 的 GIL 限制对纯 CPU 密集型的 for 循环多线程并不能提速要用多进程才行。如果 N 很大且机器有多核可以按分段筛的思路把区间分给多个进程各自筛完把质数段合并。进程间通信会有额外开销所以只有段数多、每段计算量大时才划算。我自己的经验是单机四核环境下把 10^8 的筛分任务拆成 4 段并行总共能提速到 2.5 倍左右而不是理论 4 倍原因是合并和启动进程消耗了一部分时间。如果计算资源紧张还是优先考虑优化单线程算法本身。7.3 预计算质数表工程里最常见的套路在真实业务里很多场景的“求第 N 个质数”其实根本不是动态计算而是提前算好一张足够大的质数表存进文件运行时只做一次二分查找或者数组索引。比如某些应用只需要前 100 万个质数那就在部署时跑一段离线脚本生成一个二进制文件启动时加载到内存查询时 O(1) 返回。这样就把几十秒的计算时间转移到部署初始化阶段线上接口的响应时间能压到微秒级。这种预计算方案特别适合需要频繁查询不同 N 的质数、N 的范围固定、内存充足的服务端程序。我之前参与过一个模拟项目需要对大量随机 N 做质数判断当时直接生成了一亿以内质数表查询速度比现场筛法快几千倍内存也就 100MB 出头效果非常好。8. 常见问题与排查技巧实录8.1 筛出的最后一个质数不对或者漏了 2、3很多人第一次写完筛法验证 100 以内质数时发现结果对不上大概率是下标边界写错了。比如range(2, limit1)和range(2, limit)的区别要搞清楚limit 本身可能是质数所以一定要包含 limit。另一个常见错误是把is_prime[0]和is_prime[1]初始化漏掉这两个位置虽然不在筛分循环里出现但最后列表推导式会把 0 和 1 也收进结果导致结果为 [0, 1, 2, 3,……]。这个错误很隐蔽建议大家测试时用assert sieve(20) [2, 3, 5, 7, 11, 13, 17, 19]这种硬断言来排查。8.2 求第 N 个质数时limit 不够怎么办我遇到过一些同学直接用质数定理算出 limit然后去筛结果返回的质数列表长度小于 N代码就报越界错误。解决方案正如前面所说设置一个循环如果len(primes) n就让 limit 翻倍重新筛。这里需要注意一个细节翻倍以后之前筛过的数组会被丢掉重新建如果 limit 从 1000 翻到 2000重建成本不高但是从 1 亿翻到 2 亿重建成本很高。所以更好的办法是对 limit 进行一个更保守的估计——多乘一个系数比如 1.1~1.2力争一次筛成就地返回。质数定理给出的值虽有偏差但偏差比通常不会超过 10%乘以 1.2 基本安全。8.3 Python 的布尔列表为什么比 bytearray 慢那么多我测试过同样逻辑下list[True] * (n1)和bytearray(b\x01) * (n1)的筛分耗时后者通常能快 1.5 到 2 倍原因在于布尔列表的每个元素是一个独立 Python 对象修改它涉及到引用计数和对象池操作而bytearray的每个元素是 C 层面的原生字节修改时直接在内存对应位置写值。所以如果你的程序性能敏感首先把布尔列表换掉。这是性价比最高的一个优化几乎不增加代码复杂度。8.4 不要用[False] * n再逐个赋值为 True 的倒置写法有些人习惯把数组初始化为全 False然后遇到一个质数就把它对应位置改成 True。这在逻辑上没问题但写起来麻烦而且容易在循环里漏改。反过来初始化为全 True只需要在筛分时把合数位置改成 False逻辑更契合“删除合数”的筛法思想。两种写法本质等价但从直觉和可读性上我强烈建议用全 True 初始化。9. 埃氏筛的现实应用它不只是算法题里的玩具很多初学者刷完筛法之后觉得它在实际工作中根本用不上那就大错特错了。质数在现代计算机科学里处处露脸RSA 加密需要生成两个大质数随机数的种子生成可能用到质数表某些哈希表设计里用质数作为容量可以让元素分布更均匀数据分片时用一致哈希的分隔数也需要质数。还有数学软件做数论计算时光是质数表这一项就要依赖高效筛法。举一个非常具体的例子如果你设计一个哈希表容量选择是一个质数可以减少因为取模运算带来的碰撞。那么问题来了给定一个预期存储量 10000你希望找到一个不小于 10000 的质数作为容量。这时候你就可以用埃氏筛把 10000 附近的所有质数筛出来找到第一个满足条件的。这种需求在底层存储引擎设计中会经常遇到。类似地在图像处理或密码学中需要查找特定范围内的孪生质数、质数对时埃氏筛也是基础工具。我曾在某真实业务里处理过一个需求需要生成一组既无规律又不重复的标识码方案是把一个大数区间做质数筛然后用质数序列经过变换作为 ID 池。当时直接用埃氏筛分段筛出两千万以内的全部质数存成文件之后为每个新请求分配一个不重复的质数 ID既能保证不冲突又带一点随机性。这个场景不需要多高深的数学但体现了一个思路筛法是很多“找质数、用质数”场景的地基。10. 一个更实用的扩展生成前 N 个质数的生成器有时候你并不关心第 N 个质数是几而是想持续地按顺序拿到质数流。上面那种“先估算 limit 再筛”的做法就不适合了因为你不知道流要多长。这时候可以用一个无限质数生成器。思路也很简单维护一个小根堆堆里存放即将到来的合数。从 2 开始边生成边把当前质数的倍数推入堆堆顶就是下一个合数的位置一旦当前候选数不等于堆顶就说明它是质数。这个算法本质上是一种增量式埃氏筛也叫单调队列筛它能在 O(1) 平均时间生成下一个质数内存占用与已生成质数的平方根相关非常优雅。不过这种生成器写起来稍显复杂而且 Python 实现下性能不一定比“按预估批量筛”更好。如果只是需要一次性取前 M 个质数我仍然建议老老实实估算 limit 再筛。如果你需要的是类似流式处理比如不断请求下一个质数、并应用到某个在线算法中那么生成器会有更多用武之地。11. 个人踩坑总结与最终建议最后分享几点个人在实际学习和项目中总结出的经验。第一学习埃氏筛时不要急着背代码先把“为什么从 i*i 开始标记”“为什么到 sqrt(n) 就能停”这两个问题彻底想明白。理解了这两点你写出来的代码自动就是正确的而且很难忘。第二在面试或者比赛场景下优先使用最朴素的埃氏筛实现不要一上来就搞奇偶分离加字节数组的高复杂度版本。先把功能正确跑通再根据面试官的问题决定要不要优化。很多时候面试官只是想考察你知不知道埃氏筛而不是想看你炫技。第三Python 环境下使用bytearray是一个性价比极高的选择几乎不影响可读性却能省大量内存和不少时间。如果你做在线算法题时遇到内存限制比较紧第一个想到的优化就应该是它而不是去修改逻辑。第四求第 N 个质数时越界保护别偷懒。哪怕输入数据保证 N 很大写一个通用的if n 1: raise ValueError成本非常低但它能避免午夜收到报警邮件。第五不要迷信“必须用线性筛”。在很多工程场景下埃氏筛足够快线性筛的额外能力比如求最小质因子你用不上强行用反而增加出错概率。工具适配需求才是最重要的。如果你读完这篇文章想立刻动手试试我建议你做两件事第一手写一个基础埃氏筛用 100、1000、10000 三个范围的已知质数结果去验证第二对比一下把bytearray换成list之后耗时的变化。跑通这两个练手任务之后你在埃氏筛这块的基本功就算真正夯实了。后面如果遇到更大规模的需求再来翻这篇文章的进阶优化部分也不迟。