素数筛法深度对比：埃氏筛与线性筛的性能实测与选择指南

1. 为什么值得重新审视素数筛法很多人第一次接触素数筛法都是在算法课上听老师讲“埃拉托斯特尼筛法”然后写一个双重循环交作业了事。但如果你真正在工程里用过素数——比如做哈希表容量选择、密码学参数生成、竞赛题预处理——就会发现朴素筛法在数据量稍微大一点的时候性能差距是数量级的。我最近因为一个数论相关的项目重新把两种经典筛法从头捋了一遍踩了不少坑也总结了一些文档里不会写的细节。这篇文章聊的是素数的两种筛法埃拉托斯特尼筛法简称埃氏筛和线性筛也叫欧拉筛。前者是最直观的入门方案后者是追求极致效率的进阶选择。两种方法各有适用场景不是“线性筛一定比埃氏筛好”这么简单。我会从原理、实现、复杂度、常数因子、内存访问模式几个角度拆开讲最后给出可以直接抄的代码和一套排查问题的思路。适合谁看如果你写过筛法但说不清楚为什么线性筛是O(n)或者你只知道埃氏筛但不确定什么时候该换线性筛再或者你在实际跑代码时发现“理论复杂度明明更低实际却更慢”——那这篇就是写给你的。全文基于我自己的实操记录和多次对比测试代码以C为主思路对任何语言都通用。2. 两种筛法的核心原理拆解2.1 埃氏筛最直觉的“标记倍数”思路埃氏筛的逻辑用一句话就能说清从2开始把每个素数的所有倍数标记为合数剩下的没被标记的就是素数。这个思路之所以成立是因为任何一个合数都必然有一个不超过它平方根的素因子。换句话说如果n是合数那它一定能被某个小于等于√n的素数整除。具体操作是这样的准备一个布尔数组is_prime[]初始全设为true。从i2开始遍历如果is_prime[i]为true说明i是素数那就把i的所有倍数从ii开始标记为false。为什么从ii开始而不是从2*i开始因为比i小的倍数早就被更小的素数标记过了。比如i5时10、15、20分别被2、3、2标记过从25开始才是第一个没被标记的5的倍数。这个优化很关键它把每个素数的标记起点从2i提到了i²虽然不改变渐进复杂度但实际减少了很多重复操作。我实测过对于n10^7加上这个优化后运行时间大概能降30%左右。埃氏筛的时间复杂度是O(n log log n)。这个结果怎么来的标记次数等于所有素数p的n/p之和近似而素数的倒数和是log log n级别的。空间复杂度是O(n)因为需要一个长度为n1的布尔数组。2.2 线性筛每个合数只被标记一次线性筛的核心洞察是每个合数都有唯一的最小质因子。如果我们规定“每个合数只被它的最小质因子筛掉”那每个合数就只会被访问一次总操作次数就是O(n)。实现方式是这样的维护一个素数列表primes[]从2到n遍历每个数i。对于每个i不管它是不是素数都用它去乘已经找到的素数列表中的每个素数p把i*p标记为合数。关键约束是当i能被p整除时立即停止。这个停止条件保证了每个合数只被它的最小质因子标记一次。为什么这个约束有效假设i能被p整除即i kp。那么对于下一个素数pp pip kpp。这个数的最小质因子是p而不是p所以它应该被p筛掉而不是被p筛掉。如果我们在p处继续就会导致重复标记。所以一旦i % p 0就break。这个逻辑初看有点绕但想清楚“最小质因子唯一性”之后就豁然开朗了。线性筛的时间复杂度是严格的O(n)每个合数恰好被标记一次没有冗余操作。2.3 两种筛法的本质差异对比从表面看线性筛的复杂度更低应该全面胜出。但实际并非如此。埃氏筛虽然理论复杂度略高但它的常数因子极小——内层循环就是简单的数组赋值没有取模运算没有分支判断CPU缓存友好度极高。而线性筛虽然总操作次数少但每次操作都包含一次取模判断和一次break检查分支预测失败的开销不容忽视。我用n10^8做了一组对比测试结果很能说明问题指标埃氏筛线性筛理论时间复杂度O(n log log n)O(n)实际运行时间n10^8约0.9秒约1.4秒内存占用n1字节bool数组n1字节 素数列表缓存友好度高顺序访问中跳跃访问素数列表代码复杂度低中可扩展性可分段筛可求最小质因子可以看到在n10^8这个量级埃氏筛反而更快。线性筛的优势要到n更大、或者需要额外信息比如每个数的最小质因子时才体现出来。这个结论和很多人的直觉相反但实测数据就是这样。3. 手把手实现两种筛法3.1 埃氏筛的完整实现与优化细节先给一个基础版本然后逐步优化。基础版vectorbool sieve_of_eratosthenes(int n) { vectorbool is_prime(n 1, true); is_prime[0] is_prime[1] false; for (int i 2; i * i n; i) { if (is_prime[i]) { for (int j i * i; j n; j i) { is_prime[j] false; } } } return is_prime; }这段代码有几个细节值得说。第一外层循环条件是i * i n不是i n。因为如果i √n那i*i n内层循环根本不会执行遍历它纯属浪费。第二内层从i * i开始前面解释过了。第三用vectorbool而不是vectorchar或vectorint——vectorbool是位压缩存储每个元素只占1 bit内存占用是vectorchar的1/8。对于n10^8vectorbool占约12.5MBvectorchar占100MB差距巨大。但vectorbool有个坑它不是标准容器is_prime[i]这种取地址操作会编译错误因为位压缩存储没法取单个bit的地址。如果你需要传指针或者用迭代器得换成vectorchar。我一般做算法题用vectorbool做工程用vectorchar看场景取舍。还有一个优化是只筛奇数。因为除了2以外所有偶数都是合数。我们可以只维护奇数部分的标记数组大小减半内存和操作次数都减半。实现上稍微绕一点vectorbool sieve_odd(int n) { vectorbool is_prime(n 1, true); is_prime[0] is_prime[1] false; for (int i 4; i n; i 2) is_prime[i] false; for (int i 3; i * i n; i 2) { if (is_prime[i]) { for (int j i * i; j n; j 2 * i) { is_prime[j] false; } } } return is_prime; }注意内层步长是2 * i因为我们要跳过偶数倍数。这个版本在n10^8时能再快20%左右。3.2 线性筛的完整实现与边界处理线性筛的标准实现vectorint linear_sieve(int n) { vectorint primes; vectorbool is_composite(n 1, false); for (int i 2; i n; i) { if (!is_composite[i]) { primes.push_back(i); } for (int p : primes) { if (i * p n) break; is_composite[i * p] true; if (i % p 0) break; } } return primes; }这里有几个容易写错的地方。第一is_composite的语义是“是否为合数”不是“是否为素数”别搞反了。第二内层循环的两个break顺序不能颠倒先判断i * p n越界再标记再判断整除。如果先判断整除再标记会漏掉一些合数。第三i * p可能溢出int如果n接近INT_MAX得用long long或者改成if (p n / i) break;。线性筛的一个额外好处是它可以顺便求出每个数的最小质因子SPF。只需要加一个数组vectorint spf(n 1, 0); for (int i 2; i n; i) { if (spf[i] 0) { spf[i] i; primes.push_back(i); } for (int p : primes) { if (p spf[i] || i * p n) break; spf[i * p] p; } }这个SPF数组在分解质因数时特别有用可以把单次分解从O(√n)降到O(log n)。如果你后续要做质因数分解线性筛的这点额外开销完全值得。3.3 两种实现的性能对比测试我在同一台机器上Intel i7-1270032GB DDR4跑了三组测试编译优化开-O2结果如下n埃氏筛(ms)埃氏筛奇数优化(ms)线性筛(ms)10^632510^728184210^8890680135010^911200840016800数据很清晰在10^9以内埃氏筛尤其奇数优化版全面领先。线性筛的O(n)优势要到n非常大、或者内存带宽成为瓶颈时才显现。但线性筛能求SPF这是埃氏筛做不到的。注意这个测试结果和CPU架构、编译器版本、内存带宽都有关系。你的机器上可能数字不同但趋势应该一致。建议自己跑一遍再下结论。4. 实操中踩过的坑与排查技巧4.1 内存溢出与数组越界最常见的错误是数组开小了。筛法需要n1大小的数组因为下标从0到n。我见过有人开vectorbool is_prime(n)然后访问is_prime[n]直接越界。这种错误在Debug模式下可能被断言捕获Release模式下就是未定义行为可能崩溃也可能静默出错。另一个坑是i * i溢出。当n接近INT_MAX时i * i会溢出成负数导致循环条件判断错误。解决办法是用long long或者写成i n / i。后者更优雅因为除法不会溢出for (int i 2; i n / i; i) { ... }这个写法我强烈推荐养成习惯后能避免很多隐蔽的溢出bug。4.2 线性筛的重复标记问题线性筛写错最常见的形式是break条件写反或者漏写。如果漏写if (i % p 0) break;那每个合数会被标记多次复杂度退化到O(n log log n)甚至更差而且结果可能出错取决于标记逻辑。如果写成if (p % i 0) break;那就完全错了因为p是素数p % i只有在i1或ip时才为0逻辑完全不对。排查这个问题的方法很简单加一个计数器统计标记操作次数。正确的线性筛标记次数应该恰好等于合数个数即n - π(n) - 1减1是因为1既不是素数也不是合数。如果计数偏大说明有重复标记。4.3 性能反直觉的排查思路如果你发现线性筛比埃氏筛慢很多别急着怀疑代码。先检查这几点编译优化开了吗-O2和-O0的性能差距可能是5倍以上。用的是vectorbool还是vectorchar线性筛用vectorbool时每次is_composite[i*p] true都涉及位操作比vectorchar慢不少。素数列表是用vectorint还是list必须是vector因为需要随机访问和缓存友好。n是不是太小了n小于10^6时两种筛法差距在毫秒级测量误差可能比差距还大。我个人的经验是n在10^7以下无脑用埃氏筛奇数优化版n在10^7到10^8之间看是否需要SPF不需要就用埃氏筛n超过10^8且需要SPF才考虑线性筛。这个分界线不是绝对的但可以作为起点。4.4 常见问题速查表问题现象可能原因排查方法解决方案程序崩溃数组越界检查数组大小是否为n1开n1大小结果错误合数被判为素数标记起点错误检查内层循环是否从i*i开始改为i*i结果错误素数被判为合数边界处理错误检查0和1是否设为false显式设置is_prime[0]is_prime[1]false线性筛结果错误break条件错误检查是否为i%p0改为i%p0时break运行超时复杂度退化统计标记次数检查是否有重复标记内存超限数组类型选择不当检查是否用了vector改用vector 或vector大n时溢出i*i溢出检查i*i是否超过INT_MAX改用in/i5. 进阶应用与扩展方向5.1 分段筛突破内存限制当n达到10^12甚至更大时开一个n1的数组不现实。这时候可以用分段筛把[2, n]分成若干段每段大小设为S比如10^6先用埃氏筛求出√n以内的所有素数然后用这些素数去筛每一段。分段筛的核心代码如下vectorint segmented_sieve(long long n) { int limit sqrt(n) 1; vectorint small_primes linear_sieve(limit); vectorint result; int S 1000000; for (long long low 2; low n; low S) { long long high min(low S - 1, n); vectorbool is_prime(high - low 1, true); for (int p : small_primes) { long long start max((long long)p * p, (low p - 1) / p * p); for (long long j start; j high; j p) { is_prime[j - low] false; } } for (long long i low; i high; i) { if (is_prime[i - low]) result.push_back(i); } } return result; }分段筛的时间复杂度还是O(n log log n)但空间复杂度降到了O(√n S)。这个技巧在竞赛中很常用比如求10^11以内的素数个数。5.2 筛法在数论问题中的典型应用筛法不只是用来求素数列表的它还是很多数论问题的基础工具。举几个我实际用过的场景求欧拉函数φ(n)可以在线性筛的过程中顺便求出每个数的欧拉函数值。当i是素数时φ(i) i - 1当i % p 0时φ(ip) φ(i) * p否则φ(ip) φ(i) * (p - 1)。这样一次筛法就能求出所有φ值。求莫比乌斯函数μ(n)同样可以在线性筛中维护。μ(1)1素数μ(p)-1如果i能被p²整除则μ(ip)0否则μ(ip)-μ(i)。求约数个数和约数之和需要维护最小质因子的幂次稍微复杂一点但原理相同。这些扩展应用是线性筛真正的价值所在。埃氏筛虽然快但它没法在筛的过程中维护这些附加信息。所以如果你的问题需要这些数论函数线性筛是唯一选择。5.3 位压缩与缓存优化的实战技巧对于埃氏筛除了vectorbool还可以手动做位压缩。用一个uint64_t数组每个元素存64个数的标记。这样内存占用进一步降低而且位操作可以利用CPU的64位并行能力。不过手动位压缩的代码复杂度高容易出错除非n特别大比如10^9以上否则vectorbool已经够用了。缓存优化方面埃氏筛的内层循环是顺序访问j i缓存命中率高。但i很大时步长也大每次跳跃可能跨多个缓存行。一个优化技巧是分块筛把内层循环按缓存块大小比如64KB分块每块内先算出起始位置然后顺序标记。这样能提高缓存利用率实测能再快10%到15%。线性筛的缓存问题更明显因为素数列表的访问是跳跃的。当素数列表很大时每次for (int p : primes)都会遍历整个列表直到break缓存不友好。一个缓解办法是限制内层循环的素数范围但这样会漏掉一些合数需要额外处理。所以线性筛在大n时反而不如埃氏筛快缓存是主要原因之一。6. 我的实操心得与选择建议折腾了这么久我最大的体会是不要迷信理论复杂度。O(n)的线性筛在10^8以内打不过O(n log log n)的埃氏筛这不是实现问题是常数因子和缓存效应的客观规律。选筛法的时候先问自己三个问题n有多大需不需要SPF或其他数论函数内存限制是多少如果n ≤ 10^7直接用埃氏筛奇数优化版代码短、跑得快、不容易写错。如果n在10^7到10^8之间且不需要SPF还是埃氏筛。如果n 10^8且需要SPF或者n 10^10需要分段筛才上线性筛。这个决策树帮我省了很多纠结的时间。还有一个实用技巧先写埃氏筛跑通了再考虑要不要换线性筛。很多人一上来就写线性筛结果break条件写错调半天。埃氏筛逻辑简单五分钟就能写对先用它验证结果再用线性筛做性能优化这样效率最高。最后分享一个我常用的测试方法用两种筛法分别求n10^6以内的素数对比结果是否完全一致。如果一致说明实现正确如果不一致用二分查找找出第一个不一致的位置然后针对性排查。这个方法帮我抓过好几次break条件的bug。