埃氏筛法实战指南：从原理到优化，避开边界与内存的坑

埃氏筛法这个题目，我在不同场合被问过不下十次。有意思的是，问的人背景差异极大：有刚学编程三个月、在刷算法题时被超时卡住的新手，也有写了五六年业务代码、突然要处理一批数据清洗任务的老手。他们的问题殊途同归——知道有这么个东西，知道它“很快”，但真到自己动手写的时候，要么边界写错，要么内存炸掉，要么跑出来的结果莫名其妙少几个数。这篇东西就是把这些年我踩过的、见过的坑，连同筛法本身的来龙去脉，一次性讲透。

先说清楚它是什么。埃氏筛法（Sieve of Eratosthenes）是一种用来批量找出某个范围内所有素数的经典算法，核心思路朴素到近乎直觉：把从2开始的自然数排成一列，2是素数，那就把2的所有倍数划掉；下一个没被划掉的是3，3是素数，再把3的所有倍数划掉；依此类推，最后没被划掉的都是素数。它解决的问题很具体——当你需要的不是“判断某一个数是不是素数”，而是“把一百万以内、一亿以内的素数全找出来”时，逐个试除的做法会慢到让人怀疑人生，而筛法能把复杂度压到接近线性对数级别。适合谁看？我的判断是：正在学算法与数据结构的学生、需要做数据预处理的后端开发者、对性能敏感且经常和整数打交道的人，以及任何想搞明白“为什么一个两千多年前的算法今天还在被使用”的好奇者。下面我按设计思路、核心细节、实操实现、问题排查四个层面展开，中间会穿插大量可以直接抄走的代码和参数选择依据。

1. 整体设计与思路拆解

1.1 为什么是“筛”而不是“判”

要理解埃氏筛法的设计，得先理解它和“单点判素”的本质区别。判断一个数 n 是不是素数，常规做法是从 2 试除到 √n，复杂度是 O(√n)。如果你要找出 N 以内的所有素数，对每个数都做一次单点判断，总复杂度大约是 O(N√N)。N 取一百万时，这个量级已经很难受了；N 取一亿，基本可以放弃。

筛法的聪明之处在于把“判断”变成了“排除”。它不再对每个数单独提问“你是不是素数”，而是反过来：既然2是素数，那2的倍数一定不是素数，一次性全部标记掉。这个视角的转换带来的是工作量的急剧下降——每个合数只会被它的素因子“划掉”，而不是被反复试除。用生活化的类比：单点判素像是挨家挨户敲门问“你家有没有违禁品”，筛法像是发现一个源头后直接封掉整条供应链，效率不在一个量级。

这里有个关键的设计取舍值得说清楚。筛法本质上是用空间换时间：它需要一块长度为 N+1 的布尔数组来记录每个数“是否被划掉”。这块内存是实打实的开销，N 取一亿时，即使用位图压缩也要十几兆。所以筛法不是万能的——如果你的内存极其紧张，或者你只需要判断极少数几个数，单点判素反而更合适。我在实际项目里就遇到过这种权衡：一个嵌入式场景，内存只有几百KB，最后放弃了筛法，改用米勒-拉宾做概率判素。工具没有优劣，只有匹配与否。

1.2 复杂度背后的数学直觉

很多人背过结论：埃氏筛法的时间复杂度是 O(N log log N)。这个结论怎么来的，值得掰开说，因为它直接决定了你该怎么优化。

筛法的核心操作是“划掉倍数”。2 的倍数要划掉约 N/2 个，3 的倍数约 N/3 个，5 的倍数约 N/5 个……把所有素数的贡献加起来，总划除次数约等于 N × (1/2 + 1/3 + 1/5 + 1/7 + …)。这个和式里，素数倒数的和发散得很慢，数学上可以证明它约等于 log log N。所以总操作量是 O(N log log N)。log log N 增长极慢——N 是一百万时，log log N 大约只有 2.6；N 是一亿时，也就 3 左右。这就是为什么筛法在很大范围内都表现得极其稳定。

理解了这个推导，你就能明白优化的方向在哪：减少不必要的划除。最典型的浪费是，划到某个素数 p 时，其实不需要从 2p 开始划，而应该从 p² 开始。因为所有小于 p² 的 p 的倍数，比如 2p、3p、…、(p-1)p，它们的较小因子都小于 p，早就被更小的素数划掉了。这个优化不改变复杂度量级，但能砍掉大量重复劳动，实测能省下相当可观的时间。另一个方向是只处理奇数，把数组长度减半，这个后面实操部分会详细讲。

1.3 边界与范围的取舍逻辑

设计筛法时，有几个边界决策必须提前想清楚，否则代码跑起来就是错的。

第一个是数组该开多大。要找 N 以内的素数（含 N），数组长度必须是 N+1，下标从 0 到 N。很多人习惯开 N，结果漏掉了 N 本身，如果 N 恰好是素数就会少一个。我见过不止一个新手在这里栽跟头，排查半天以为是算法写错了，其实是数组越界少算了一个。

第二个是0 和 1 的处理。它们不是素数，但也不是合数，筛法里通常直接把标记数组的这两个位置初始化为“非素数”。这一步如果忘了，后面统计素数个数时会多出两个，输出结果看着“差不多对”但就是不对，这种错误最难查。

第三个是上界到底取到哪。划除倍数时，外层循环的素数 p 只需要枚举到 √N。因为如果 p > √N，那么 p² > N，从 p² 开始划已经超出范围了，没有任何意义。这个边界如果写成 N，程序不会报错，但会白跑很多轮空循环。我在早期代码里就犯过这个错，N 取一千万时多跑了将近一半的无用循环，性能直接腰斩。

2. 核心细节解析与实操要点

2.1 标记数组的选型：布尔数组还是位图

最直观的实现是用一个布尔数组is_prime[N+1]，每个元素占一个字节。N 取一亿时，光这个数组就是 100MB 左右，对普通机器还行，但对内存敏感的场景就偏重了。

更紧凑的做法是用位图（bitset），每个数只占一位，内存直接降到原来的八分之一。一亿个数只需要约 12.5MB。代价是读写时要多做位运算，代码稍微复杂一点，单次访问略慢，但整体因为缓存命中率提升，实测往往反而更快。我的经验是：N 小于一千万时，布尔数组足够用，代码简单不易错；N 上到亿级，位图带来的内存收益非常明显，值得多写那几行位运算。

还有一种折中方案是只存奇数。因为除了2以外所有素数都是奇数，数组下标 i 对应真实数字 2i+1，长度直接减半。这个技巧在竞赛和性能敏感场景里很常见，配合位图能把一亿以内的筛法内存压到 6MB 出头。但它会让下标换算变复杂，代码可读性下降，团队协作时要权衡——如果这段代码以后要给别人维护，我倾向于优先保证清晰，除非性能确实是瓶颈。

2.2 从 p² 开始划的关键细节

前面提到划除应从 p² 开始，这个细节的实现有个容易忽略的点：p² 可能溢出。当 p 接近 √N 时，p² 本身还在 int 范围内；但如果你的 N 很大、用了 32 位整数，p 稍大一点 p² 就可能溢出成负数，导致数组越界或者死循环。稳妥的写法是在计算前先判断p <= N / p，用除法代替乘法来规避溢出。这个技巧在整数运算里非常通用，值得养成习惯。

另外，从 p² 开始划之后，内层循环的步长仍然是 p，即for (j = p*p; j <= N; j += p)。这里 j 的类型要足够大，如果 N 超过 int 上限，j 必须用 64 位整数，否则 j += p 累加过程中会溢出回绕，造成死循环。我排查过一次这种问题，现象是程序卡死不动，查了很久才发现是整数溢出，教训很深。

2.3 外层循环的终止条件

外层循环写成for (p = 2; p * p <= N; p++)是最常见的写法，但同样有溢出隐患——p*p 在 p 较大时可能溢出。更稳的写法是for (p = 2; p <= N / p; p++)。这两种写法在小数据量下没区别，但当你把 N 调到接近整数上限时，前者会出错，后者不会。这种“平时看不出、极端情况才爆”的坑，恰恰是最该提前规避的。

还有一个细节：外层循环里，如果is_prime[p]已经是 false，说明 p 是合数，直接跳过，不用划它的倍数。这一步判断不能省，否则合数也会去划倍数，虽然结果不会错（合数的倍数本来就被更小的素因子划过了），但白白浪费大量时间。我见过有人为了“代码简洁”把这行判断删掉，结果性能掉了三成。

2.4 内存访问的局部性考量

这一点偏进阶，但对大 N 场景影响很大。筛法划除时，访问模式是j, j+p, j+2p, …，步长为 p。当 p 很小时（比如2、3），访问是连续的，缓存友好；当 p 很大时，每次跳跃 p 个位置，缓存命中率急剧下降。这是筛法在大 N 下性能不如理论预期的原因之一。

缓解办法是分块筛（segmented sieve）：把大范围切成若干小块，每块单独筛，块大小选得能塞进 CPU 缓存。这样每次处理的数据都在缓存里，访问局部性大幅改善。分块筛的代码复杂度明显上升，需要维护每块的起始偏移和基础素数表，一般场景用不上，但如果你要筛十亿以上的范围，这是绕不开的优化。我在一个数据统计任务里用过，十亿范围从原来的几十秒压到了十几秒，收益很实在。

3. 实操过程与核心环节实现

3.1 基础版本的完整实现

先给一个最朴素、最不容易出错的版本，适合作为理解和验证的基准。语言用 Python，因为它可读性最好，逻辑一目了然。

def sieve_basic(n): if n < 2: return [] is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = False p = 2 while p * p <= n: if is_prime[p]: for j in range(p * p, n + 1, p): is_prime[j] = False p += 1 return [i for i in range(2, n + 1) if is_prime[i]]

这段代码有几个点值得对照前面的分析看：数组开了 n+1；0 和 1 显式置为 False；外层循环条件是p * p <= n；内层从p * p开始。这四点是正确性的骨架，缺一不可。跑一下sieve_basic(30)，输出应该是[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]，可以拿这个当冒烟测试。

Python 版本胜在清晰，但性能一般，N 取一千万时可能要跑好几秒。如果只是学习或小规模使用，这个版本完全够用。真要上规模，得换编译型语言或者用更紧凑的数据结构。

3.2 性能优化版本的实现

下面这个 C 风格版本（用 Python 的 array 模拟紧凑存储，逻辑与 C 一致）体现了前面讲的几个优化：只处理奇数、位图思想、从 p² 开始。

def sieve_odd(n): if n < 2: return [] if n == 2: return [2] size = (n + 1) // 2 is_prime = [True] * size is_prime[0] = False # 对应数字 1 limit = int(n ** 0.5) for i in range(1, (limit + 1) // 2 + 1): if is_prime[i]: p = 2 * i + 1 start = (p * p) // 2 for j in range(start, size, p): is_prime[j] = False result = [2] for i in range(1, size): if is_prime[i]: result.append(2 * i + 1) return result

这个版本的下标映射是：数组下标 i 对应真实数字 2i+1。所以 i=0 对应1（非素数），i=1 对应3，i=2 对应5，依此类推。内层起始位置(p*p)//2的推导：p² 是奇数，它对应的下标是 (p²-1)/2，而 p² 本身是奇数，所以 (p²-1)/2 和 p²//2 在整数除法下相等，用后者更简洁。步长是 p，因为相邻两个 p 的奇数倍之间差 2p，对应下标差 p。

这个版本的内存是基础版的一半，速度也快不少。实测 N 取一千万，基础版 Python 要几秒，这个版本能压到一秒出头。当然，真要极致性能还是得用 C 或 Rust，Python 的解释开销摆在那。

3.3 参数选择与规模对照

不同 N 下该选哪种实现，我整理了一个对照表，都是实测或根据经验估算的量级，供参考。

这张表的使用方式是：先看你的 N 落在哪一档，再决定要不要上优化。我的建议是不要过早优化——如果 N 只有一百万，写个基础版跑几十毫秒就完事了，没必要为了那点性能把代码搞得复杂难维护。优化的收益要和维护成本一起算账。

3.4 验证与测试的实操方法

写完筛法，怎么确认它是对的？我习惯用三层验证。

第一层是小范围手算对照。N 取 30、50、100，手工列出素数或者查现成的素数表，逐个比对。这一步能抓住绝大多数边界错误，比如漏掉 N 本身、0 和 1 没处理。

第二层是交叉验证。用筛法的结果去和单点判素的结果比对，对每个数都判断一次，看两边是否一致。单点判素虽然慢，但逻辑简单、不容易错，是很好的参照物。代码大概是这样：

def is_prime_single(x): if x < 2: return False i = 2 while i * i <= x: if x % i == 0: return False i += 1 return True def cross_check(n): sieve_result = set(sieve_basic(n)) for x in range(2, n + 1): if (x in sieve_result) != is_prime_single(x): print("不一致:", x) return False return True

第三层是性能基准。记录不同 N 下的耗时，和理论预期对照。如果 N 翻十倍、耗时翻了远超十倍，说明实现里可能有隐藏的低效操作，值得回头查。我一般会跑 N = 10万、100万、1000万三档，看增长曲线是否平滑。

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

4.1 结果少一个数或多两个数

这是最高频的问题，几乎每个新手都会遇到。症状是：输出的素数列表看着挺对，但个数对不上。

少一个数，八成是数组开成了 N 而不是 N+1，导致 N 本身没被检查。如果 N 恰好是素数，就漏了。多两个数，基本可以断定是 0 和 1 没被标记为非素数。这两个错误的共同点是“结果看起来合理”，所以特别隐蔽。排查方法很简单：拿 N=10 测一下，正确结果是[2,3,5,7]四个数，如果输出是[0,1,2,3,5,7]就是多两个，如果 N=7 时输出没有7就是少一个。

4.2 程序卡死或跑得异常慢

卡死最常见的原因是整数溢出导致的死循环。前面提过，j += p在 j 接近整数上限时可能回绕成负数，然后循环条件永远成立。另一个原因是外层循环条件写成了p <= n而不是p * p <= n，导致对每个 p 都去划倍数，虽然不会死循环，但 N 大时会慢到像卡死。

排查这类问题，我的习惯是在循环里加计数器，统计内层总共执行了多少次划除。正常情况下这个数应该在 N log log N 量级，如果远超这个量级，说明有重复劳动或者循环条件写错了。这个计数器方法比盯着代码看有效得多。

4.3 内存超限

N 取到亿级时，布尔数组可能撑爆内存限制。症状是程序被系统杀掉或者抛出内存错误。解决办法按优先级排：先考虑是否真的需要一次筛完整个范围，能不能分块处理；其次换位图压缩；最后才考虑只存奇数。这三招可以叠加使用。

有个容易忽略的点：Python 的 list of bool 其实每个元素是一个对象引用，内存开销远大于“一个字节”。真正省内存要用bytearray或者array模块。我见过有人用 list 存一亿个布尔值，内存直接吃掉几个 G，换成 bytearray 后降到一百多兆。这个坑在 Python 里特别常见，值得单独记一笔。

4.4 常见问题速查表

4.5 几个容易被忽略的实操心得

第一个心得：先用小数据把逻辑跑通，再上大规模。我见过太多人一上来就拿一亿去测，结果程序崩了，根本分不清是逻辑错还是资源不够。正确的顺序是 N=30 验证正确性，N=10万 验证性能趋势，最后才上目标规模。

第二个心得：筛法的结果可以复用。如果你要多次查询“某数是不是素数”，筛一次存下来，后续查询就是 O(1)。这个模式在需要频繁判素的场景里非常划算，比每次单点判素快得多。但如果只查一两次，筛法的预处理成本反而浪费，这时候单点判素更合适。

第三个心得：注意语言层面的陷阱。不同语言对整数溢出、数组边界、布尔存储的处理差异很大。比如在 C 里int溢出是未定义行为，可能被优化成任何结果；在 Python 里整数是任意精度，不会溢出但大数运算慢。移植代码时这些差异必须重新审视，不能想当然。

第四个心得：分块筛的块大小不是越大越好。块大小要匹配 CPU 缓存容量，通常选几十 KB 到几 MB 之间。块太大失去缓存优势，块太小则块间调度开销上升。这个参数没有万能值，得根据目标机器的缓存规格实测调优。我一般从 256KB 起步，上下浮动试几档，找耗时最低的那个。

5. 从筛法延伸出去的思考

筛法的思想其实不止用于找素数。它的本质是“用一个已知的源头，批量排除它的所有衍生结果”，这个模式在很多领域都能套用。比如做数据清洗时，发现某类脏数据的源头，可以一次性把它的所有变体标记掉；做权限校验时，某个角色被禁用，它派生出的所有权限可以批量失效。这种“源头排除”的思维，比逐个判断要高效得多。

另一个值得琢磨的点是筛法的“近似线性”特性。log log N 这个因子增长极慢，意味着筛法在极宽的范围内都保持稳定性能，这是它历经两千多年仍然是素数筛法基准的原因。现代虽然有更快的线性筛（每个合数只被划一次，复杂度 O(N)），但线性筛的常数因子更大，在小到中等规模下反而不如埃氏筛快。选算法不能只看复杂度的大 O，常数因子和实际数据规模同样重要，这是我从无数次实测里得出的体会。

最后分享一个我常用的调试小技巧：把筛法的中间状态打印出来。每处理完一个素数 p，把当前的标记数组可视化一下，看看哪些位置被划掉了。对于小 N（比如 30），这个过程能让你直观看到算法是怎么一步步收敛的，比读十遍代码都管用。理解一个算法最好的方式，永远是看着它跑一遍。