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

埃氏筛法这个题目我在不同场合被问过不下十次。有意思的是问的人背景差异极大有刚学编程三个月、在刷算法题时被超时卡住的新手也有写了五六年业务代码、突然要处理一批数据清洗任务的老手。他们的问题殊途同归——知道有这么个东西知道它“很快”但真到自己动手写的时候要么边界写错要么内存炸掉要么跑出来的结果莫名其妙少几个数。这篇东西就是把这些年我踩过的、见过的坑连同筛法本身的来龙去脉一次性讲透。先说清楚它是什么。埃氏筛法Sieve of Eratosthenes是一种用来批量找出某个范围内所有素数的经典算法核心思路朴素到近乎直觉把从2开始的自然数排成一列2是素数那就把2的所有倍数划掉下一个没被划掉的是33是素数再把3的所有倍数划掉依此类推最后没被划掉的都是素数。它解决的问题很具体——当你需要的不是“判断某一个数是不是素数”而是“把一百万以内、一亿以内的素数全找出来”时逐个试除的做法会慢到让人怀疑人生而筛法能把复杂度压到接近线性对数级别。适合谁看我的判断是正在学算法与数据结构的学生、需要做数据预处理的后端开发者、对性能敏感且经常和整数打交道的人以及任何想搞明白“为什么一个两千多年前的算法今天还在被使用”的好奇者。下面我按设计思路、核心细节、实操实现、问题排查四个层面展开中间会穿插大量可以直接抄走的代码和参数选择依据。1. 整体设计与思路拆解1.1 为什么是“筛”而不是“判”要理解埃氏筛法的设计得先理解它和“单点判素”的本质区别。判断一个数 n 是不是素数常规做法是从 2 试除到 √n复杂度是 O(√n)。如果你要找出 N 以内的所有素数对每个数都做一次单点判断总复杂度大约是 O(N√N)。N 取一百万时这个量级已经很难受了N 取一亿基本可以放弃。筛法的聪明之处在于把“判断”变成了“排除”。它不再对每个数单独提问“你是不是素数”而是反过来既然2是素数那2的倍数一定不是素数一次性全部标记掉。这个视角的转换带来的是工作量的急剧下降——每个合数只会被它的素因子“划掉”而不是被反复试除。用生活化的类比单点判素像是挨家挨户敲门问“你家有没有违禁品”筛法像是发现一个源头后直接封掉整条供应链效率不在一个量级。这里有个关键的设计取舍值得说清楚。筛法本质上是用空间换时间它需要一块长度为 N1 的布尔数组来记录每个数“是否被划掉”。这块内存是实打实的开销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.6N 是一亿时也就 3 左右。这就是为什么筛法在很大范围内都表现得极其稳定。理解了这个推导你就能明白优化的方向在哪减少不必要的划除。最典型的浪费是划到某个素数 p 时其实不需要从 2p 开始划而应该从 p² 开始。因为所有小于 p² 的 p 的倍数比如 2p、3p、…、(p-1)p它们的较小因子都小于 p早就被更小的素数划掉了。这个优化不改变复杂度量级但能砍掉大量重复劳动实测能省下相当可观的时间。另一个方向是只处理奇数把数组长度减半这个后面实操部分会详细讲。1.3 边界与范围的取舍逻辑设计筛法时有几个边界决策必须提前想清楚否则代码跑起来就是错的。第一个是数组该开多大。要找 N 以内的素数含 N数组长度必须是 N1下标从 0 到 N。很多人习惯开 N结果漏掉了 N 本身如果 N 恰好是素数就会少一个。我见过不止一个新手在这里栽跟头排查半天以为是算法写错了其实是数组越界少算了一个。第二个是0 和 1 的处理。它们不是素数但也不是合数筛法里通常直接把标记数组的这两个位置初始化为“非素数”。这一步如果忘了后面统计素数个数时会多出两个输出结果看着“差不多对”但就是不对这种错误最难查。第三个是上界到底取到哪。划除倍数时外层循环的素数 p 只需要枚举到 √N。因为如果 p √N那么 p² N从 p² 开始划已经超出范围了没有任何意义。这个边界如果写成 N程序不会报错但会白跑很多轮空循环。我在早期代码里就犯过这个错N 取一千万时多跑了将近一半的无用循环性能直接腰斩。2. 核心细节解析与实操要点2.1 标记数组的选型布尔数组还是位图最直观的实现是用一个布尔数组is_prime[N1]每个元素占一个字节。N 取一亿时光这个数组就是 100MB 左右对普通机器还行但对内存敏感的场景就偏重了。更紧凑的做法是用位图bitset每个数只占一位内存直接降到原来的八分之一。一亿个数只需要约 12.5MB。代价是读写时要多做位运算代码稍微复杂一点单次访问略慢但整体因为缓存命中率提升实测往往反而更快。我的经验是N 小于一千万时布尔数组足够用代码简单不易错N 上到亿级位图带来的内存收益非常明显值得多写那几行位运算。还有一种折中方案是只存奇数。因为除了2以外所有素数都是奇数数组下标 i 对应真实数字 2i1长度直接减半。这个技巧在竞赛和性能敏感场景里很常见配合位图能把一亿以内的筛法内存压到 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, jp, j2p, …步长为 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]]这段代码有几个点值得对照前面的分析看数组开了 n10 和 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 对应真实数字 2i1。所以 i0 对应1非素数i1 对应3i2 对应5依此类推。内层起始位置(p*p)//2的推导p² 是奇数它对应的下标是 (p²-1)/2而 p² 本身是奇数所以 (p²-1)/2 和 p²//2 在整数除法下相等用后者更简洁。步长是 p因为相邻两个 p 的奇数倍之间差 2p对应下标差 p。这个版本的内存是基础版的一半速度也快不少。实测 N 取一千万基础版 Python 要几秒这个版本能压到一秒出头。当然真要极致性能还是得用 C 或 RustPython 的解释开销摆在那。3.3 参数选择与规模对照不同 N 下该选哪种实现我整理了一个对照表都是实测或根据经验估算的量级供参考。N 的规模推荐实现内存占用约预期耗时量级10 万以内基础布尔数组100KB毫秒级100 万基础布尔数组1MB几十毫秒1000 万奇数优化5MB百毫秒级1 亿奇数 位图6-13MB秒级10 亿分块筛可控按块十秒级这张表的使用方式是先看你的 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 而不是 N1导致 N 本身没被检查。如果 N 恰好是素数就漏了。多两个数基本可以断定是 0 和 1 没被标记为非素数。这两个错误的共同点是“结果看起来合理”所以特别隐蔽。排查方法很简单拿 N10 测一下正确结果是[2,3,5,7]四个数如果输出是[0,1,2,3,5,7]就是多两个如果 N7 时输出没有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 常见问题速查表现象最可能原因排查动作结果少一个素数数组长度开成 N改为 N1用 N7 测试结果多出 0 和 1未初始化边界显式置 is_prime[0]is_prime[1]False程序卡死整数溢出或循环条件错加划除计数器检查 p*p 与 jp内存超限用 list 存布尔值换 bytearray 或位图大 N 下变慢明显缓存不友好考虑分块筛结果对但极慢外层未跳过合数补上 if is_prime[p] 判断4.5 几个容易被忽略的实操心得第一个心得先用小数据把逻辑跑通再上大规模。我见过太多人一上来就拿一亿去测结果程序崩了根本分不清是逻辑错还是资源不够。正确的顺序是 N30 验证正确性N10万 验证性能趋势最后才上目标规模。第二个心得筛法的结果可以复用。如果你要多次查询“某数是不是素数”筛一次存下来后续查询就是 O(1)。这个模式在需要频繁判素的场景里非常划算比每次单点判素快得多。但如果只查一两次筛法的预处理成本反而浪费这时候单点判素更合适。第三个心得注意语言层面的陷阱。不同语言对整数溢出、数组边界、布尔存储的处理差异很大。比如在 C 里int溢出是未定义行为可能被优化成任何结果在 Python 里整数是任意精度不会溢出但大数运算慢。移植代码时这些差异必须重新审视不能想当然。第四个心得分块筛的块大小不是越大越好。块大小要匹配 CPU 缓存容量通常选几十 KB 到几 MB 之间。块太大失去缓存优势块太小则块间调度开销上升。这个参数没有万能值得根据目标机器的缓存规格实测调优。我一般从 256KB 起步上下浮动试几档找耗时最低的那个。5. 从筛法延伸出去的思考筛法的思想其实不止用于找素数。它的本质是“用一个已知的源头批量排除它的所有衍生结果”这个模式在很多领域都能套用。比如做数据清洗时发现某类脏数据的源头可以一次性把它的所有变体标记掉做权限校验时某个角色被禁用它派生出的所有权限可以批量失效。这种“源头排除”的思维比逐个判断要高效得多。另一个值得琢磨的点是筛法的“近似线性”特性。log log N 这个因子增长极慢意味着筛法在极宽的范围内都保持稳定性能这是它历经两千多年仍然是素数筛法基准的原因。现代虽然有更快的线性筛每个合数只被划一次复杂度 O(N)但线性筛的常数因子更大在小到中等规模下反而不如埃氏筛快。选算法不能只看复杂度的大 O常数因子和实际数据规模同样重要这是我从无数次实测里得出的体会。最后分享一个我常用的调试小技巧把筛法的中间状态打印出来。每处理完一个素数 p把当前的标记数组可视化一下看看哪些位置被划掉了。对于小 N比如 30这个过程能让你直观看到算法是怎么一步步收敛的比读十遍代码都管用。理解一个算法最好的方式永远是看着它跑一遍。