素数筛法这个经典问题在 C# 里经常因为一行代码被引上热搜求 [2,N] 之间的全部素数可以用 LINQ 一行写完也可以用十几行的埃氏筛。标题里说得更夸张——1 行代码 vs 10 亿次计算效率差 1000 倍我第一次看到这个说法是持怀疑态度的毕竟 C# 再怎么说也是编译型语言一行代码能慢到哪里去直到自己搭了个基准测试环境跑了一遍才对算法复杂度四个字有了刻骨铭心的认识。这篇我把自己跑出来的数据、几种写法的完整代码、以及后续优化中踩过的坑全部分享出来尤其适合那些习惯有什么功能都先 LINQ 一把梭、又对性能敏感的同学。1. 这个标题背后到底在比什么1.1 两种思路的本质差异先把问题限定清楚我们要枚举 [2,N] 之间所有的素数。比如 N100 万要返回 78498 个素数。针对这个目标有两种截然不同的思路。第一种是逐个验证从 2 到 N 遍历每个整数单独判断它是不是素数判断方式就是试除从 2 到 sqrt(n) 的所有整数看有没有因子。第二种是批量淘汰先假设 2 到 N 全是素数然后从最小的素数 2 开始把 2 的倍数全部标记为合数再取下一个没被标记的数 3把 3 的倍数全部标记为合数以此类推最后没被标记的就是素数。这就是古希腊数学家埃拉托斯特尼发明的筛法思路。两种思路的天壤之别在于逐个验证时每个数字都是独立判定的前面做过的判断结果完全没被复用而筛法把判定过程变成了一次性标记一个合数被标记过之后后面再也不会碰它。这个差异在数据量小的时候无所谓一旦 N 涨到 10 万、100 万计算量的差距就会从几倍拉大到上千倍。1.2 为什么一行代码如此诱人又如此危险很多 C# 开发者第一反应是用 LINQ 写素数判断因为确实太优雅了var primes Enumerable.Range(2, N - 1) .Where(n n 2 || Enumerable.Range(2, (int)Math.Sqrt(n) - 1).All(d n % d ! 0)) .ToArray();短短一行可读性强没有显式循环看起来人畜无害。但问题恰恰藏在 LINQ 的实现机制里每次外层 Where 回调被调用时内层 Enumerable.Range 都会创建一个新的 Range 迭代器。N100 万时这意味着系统要创建几十万个 Range 对象调用上亿次迭代器 MoveNext同时还伴随着委托闭包捕获、状态机分配、GC 回收压力。这些开销全部叠加上去远不是少写几行代码能弥补的。我并不是说 LINQ 本身慢。LINQ 在遍历集合、筛选数据时足够简洁高效但把它用在需要大量数值计算的场景尤其是嵌套 Range 造出百万级迭代器的时候成本就完全失控了。1.3 适用场景先分清稀疏判断 vs 批量枚举这里要泼一盆冷水别看到筛法快 1000 倍就走到另一个极端把所有素数判断都改成筛法。如果你的需求是判断某个单独的数字 n 是不是素数并且 n 本身比较大比如 10 亿那么筛法并不合适——你不可能为了判断一个数去建一个 10 亿长度的数组。此时试除法、甚至更高级的 Miller-Rabin 概率素性测试才是合理选择。但如果你要做的是批量获得 [2,N] 内所有素数筛法就是碾压级方案。这也是标题里那个比较的真正含义一行 LINQ 是在对 N 个数逐个做验证而筛法是在用 O(N) 的空间换取一次标记全部解决的批处理能力。两种需求对应两种方案场景选错了性能就会断崖式下跌。2. 三种 C# 实现的完整对比实测2.1 基准测试要控制哪些变量在贴数据之前必须先说清楚测试条件不然一切数字都是耍流氓。我的测试坏境是普通开发机、.NET 8、Release x64没有附加调试器。测试方法用 Stopwatch 手动预热三次后取中位数每个 N 值单独跑避免 GC 互相干扰。真正严谨的做法是用 BenchmarkDotNet它会自动处理 JIT 预热、CPU 频率波动、Warmup 和 Iteration 统计。我这次为了快速验证用 Stopwatch 直接做核心原则有以下几条必须在 Release 模式下测试Debug 模式下 JIT 不会做内联和寄存器优化差距完全失真。必须先预热.NET 的 JIT 是运行时编译第一次调用往往比后面慢几倍。不能边测边用 IDE 调试器挂载调试器会禁用部分 JIT 优化。每个实现要在独立进程中轮换顺序测试避免垃圾回收带来的偶然性。2.2 代码逐行拆解先看第一种一行 LINQ实现public static int[] GetPrimesLinq(int max) { return Enumerable .Range(2, Math.Max(0, max - 1)) .Where(n n 2 || Enumerable.Range(2, (int)Math.Sqrt(n) - 1) .All(d n % d ! 0)) .ToArray(); }有两个边界细节容易写错。n2 时 Math.Sqrt(2) 取整为 1如果直接写 Enumerable.Range(2, (int)Math.Sqrt(n) - 1) 会得到 Range(2, 0) 空集合All 返回 true这没问题但万一代码写的是 Range(2, (int)Math.Sqrt(n) - 2)就会出现 Range(2, -1) 直接抛 ArgumentOutOfRangeException。另一个细节是 n4 时 sqrt2Range(2,1) 只包含数字 2所以 4%20 会被正确筛掉。这一行代码里的每一个边界值都是踩过坑才确认的。再看埃拉托斯特尼筛法public static bool[] GetPrimesEratosthenes(int max) { var isPrime new bool[max 1]; Array.Fill(isPrime, true); isPrime[0] isPrime[1] false; for (int i 2; (long)i * i max; i) { if (!isPrime[i]) continue; for (int j i * i; j max; j i) { isPrime[j] false; } } return isPrime; }这个实现里有一个非常关键的细节内层循环从 ii 开始而不是从 2i 开始。为什么因为 i 的较小倍数比如 2i、3i、4i……早就被比 i 更小的素数标记过了。比如 i5 时10、15、20 分别是 2 和 3 的倍数早已被置为 false完全没必要再走一遍。从 i*i 开始可以避免大量重复标记是埃氏筛性能的重要来源。之所以用 (long)i * i 而不是 i * i是因为 int 乘法在 i 超过 46340 时就会溢出变成负数导致条件判断失效。这个问题在 N 较大时非常隐蔽后面避坑部分会再展开。最后是欧拉筛也叫线性筛public static Listint GetPrimesLinear(int max) { var isComposite new bool[max 1]; var primes new Listint(); for (int i 2; i max; i) { if (!isComposite[i]) { primes.Add(i); } for (int j 0; j primes.Count; j) { int p primes[j]; long v (long)i * p; if (v max) break; isComposite[v] true; if (i % p 0) break; } } return primes; }欧拉筛的核心在于每个合数只被它的最小质因子标记一次。为了实现这一点内层循环在遇到i % p 0时会立刻 break保证合数 i*p 不会被更大的 p 再次标记。比如 i6p2 时 v12 被标记随后 i%20 触发 breakp3 就不会再去标记 18因为 18 的最小质因子是 2理应由 i9、p2 时来标记。这种精妙的控制让欧拉筛的理论复杂度来到 O(N)虽然常数比埃氏筛略大但扩展性更好。2.3 实测数据1000 倍真的存在在我本机跑出的量级大致如下不同配置机器会有浮动但相对关系非常稳定N 值一行 LINQ埃氏筛欧拉筛LINQ / 埃氏筛10^4约 11 ms约 0.05 ms约 0.04 ms约 200 倍10^5约 135 ms约 0.4 ms约 0.25 ms约 300 倍10^6约 2.8 s约 3.5 ms约 3.0 ms约 800 倍10^7预计 40 s 以上约 30 ms约 25 ms超 1000 倍这个表已经能回答标题里的问号1000 倍不仅存在在 N10^7 这个量级只会更夸张。N10^6 时 LINQ 版只跑到约 800 倍是因为那个时候内层试除的平均次数还相对小常数项占比高随着 N 继续变大渐近复杂度的差距会完全统治耗时1000 倍是起步价。3. 从复杂度推导看差距来源3.1 时间复杂度O(n√n) 与 O(n log log n)为什么不满足于跑出来是这么多而是要推导复杂度因为只有理解了复杂度你才能在任何 N 下预判性能而不是依赖一次实验。逐个试除法对每个整数 i 都要试除到 sqrt(i)总操作量近似为∑(i2..N) sqrt(i) ≈ (2/3) N^(3/2)当 N10^6 时这个值大约是 6.7 亿次取模运算。标题里说的10 亿次计算就是这么来的——如果把取模、加法、迭代器移动都算进去逼近 10 亿这个量级并不夸张。埃氏筛则完全不同。对每个素数 p它从 p² 开始标记 N/p 个倍数总操作量约等于∑(p≤N) N/p ≈ N log log NN10^6 时log log N 约为 2.6所以总操作量只有约 260 万次。6.7 亿次取模对比 260 万次标记原本是 250 倍左右的差距再乘上 LINQ 的迭代器、委托、状态机开销实测达到 800 倍甚至 1000 倍完全合情合理。3.2 每一步都在浪费反复试除与缺失状态的代价试除法最大的问题是不积累状态。你判断完 97 是素数知道了 2、3、5、7 都不能整除它可等到判断 101 时2、3、5、7 又要从头除一遍。每个数字都从零开始以前算过的结果全部丢弃。这是一种典型的无状态重复劳动。筛法恰好相反它维护了一张大表只要某个数被标记为合数后续流程就不会再操作它。整个计算是一场有组织的淘汰每个合数最多被它的某个质因子标记一次。用一个仓库类比试除法像是每次取货都要从仓库门口开始把货架数一遍筛法则像提前给所有货架贴好标签之后只需要看标签走流程。3.3 空间换时间筛法的本质筛法能用 O(N) 的布尔数组换出远超预期的性能收益本质是用空间冗余消除重复计算。在现代计算机的内存容量面前把答案缓存起来的代价往往远小于反复计算的代价。但这也带来一个边界当 N 超过内存能轻松容纳的范围比如 10^9 以上bool 数组的 1 字节/元素就会变得很昂贵。此时要么用 BitArray 把内存压缩到 1/8要么用分段筛让内存占用变成 O(sqrt(N)) 的常数级别。这些是工程化阶段要考虑的问题基础算法的复杂度逻辑始终不变。4. C# 筛法工程化的实用优化4.1 跳过偶数数组先减半埃氏筛最直觉的优化就是跳过所有偶数。2 单独拎出来之后只处理奇数。这样做数组长度直接减半外层循环次数也减半内存占用和运算次数双双下降。以 max10^7 为例布尔数组从 10 兆字节降到 5 兆字节更容易装进 CPU 缓存。访问速度的提升比想象中明显。一个常见的奇数化实现思路是把索引 i 映射到真实数 2*i1。比如索引 1 对应 3索引 2 对应 5。标记倍数时从 p² 开始步长不是 p 而是 2p因为偶数倍必然还是偶数不需要管public static Listint SieveOdd(int max) { if (max 2) return new Listint(); int half (max - 1) / 2; var isPrime new bool[half 1]; Array.Fill(isPrime, true); var primes new Listint { 2 }; for (int i 1; i half; i) { if (!isPrime[i]) continue; int n 2 * i 1; primes.Add(n); if ((long)n * n max) continue; for (long j (long)n * n; j max; j 2 * n) { int idx (int)((j - 1) / 2); isPrime[idx] false; } } return primes; }这里最隐蔽的坑是 j 2 * n 而不是 j n。如果按 j n 来跳会同时标记奇数和偶数位置索引换算会出错。效率优化不是简单加个判断就完事步长和索引映射必须同步调整。4.2 BitArray内存压缩到极致如果你要跑 N10^9 这种超大范围bool 数组的 1GB 内存可能直接让程序被操作系统换页性能从计算密集恶化成磁盘密集。这时候 BitArray 是更合适的选择它每 8 个布尔值只占 1 个字节10^9 个标记位大约 125MB。用法上几乎没有门槛var flags new BitArray(max 1, true); flags[0] false; flags[1] false; for (int i 2; (long)i * i max; i) { if (!flags[i]) continue; for (int j i * i; j max; j i) { flags[j] false; } }不过要提醒一句BitArray 的索引器内部要做位运算定位字节、定位位、读写位随机访问性能比 bool[] 慢 20% 到 30%。N 在 10^7 以内时用 bool[] 往往更快N 到了 10^8 以上内存吃紧时BitArray 的收益才真正体现。工程上没有银弹只有权衡。4.3 分段筛与并行化的边界再大的 N比如 10^10 以上BitArray 也不够用了。这时改成分段筛先只用 O(sqrt(N)) 的空间筛出 sqrt(N) 以内的素数然后每次只加载一个块区间比如 100 万个数字用之前筛出的小素数去标记这个块内的合数。内存占用被压到常数级N 可以开到很大。并行化也是很多人忍不住想做的优化但埃氏筛的前半段是强依赖的——必须从小素数开始逐步排除直接对整段数组做 Parallel.For 反而会因为共享数组竞争和错误依赖而变慢。我实践下来比较稳的做法是先顺序筛出 sqrt(N) 以内的素数然后把这些素数复制到线程局部数组每个线程处理一个独立分块互相之间不写同一段内存最后再合并结果。线程数不是越多越好在 8 核左右的机器上分块数接近核心数时收益最大再继续加大线程数会因为锁、缓存伪共享等问题出现收益递减。5. 避坑经验这些坑我全踩过5.1 LINQ 写法的隐蔽问题一行 LINQ 的陷阱不只是性能。如果你把它放到延迟执行的上下文里闭包捕获的变量也会坑人。比如你用 for 循环构建一个 selector不小心捕获了循环变量 i而 LINQ 又是延迟执行的最终所有查询可能拿到同一个 i 值。还要注意 Any 和 All 的关系。判断一个数没有因子时逻辑上应该是All(d n % d ! 0)如果你顺手写成Any(d n % d ! 0)那任何数都会返回 true——因为一个整数几乎不可能被前面所有数整除。语义差一个单词结果天差地别。另外内层 Enumerable.Range 的终点必须小心。很多写法用(int)Math.Sqrt(n)作为终点但会忘记 Range 的第二个参数是 count不是 end。你要的是包含 sqrt(n) 本身所以 count 要写(int)Math.Sqrt(n) - 1而不是(int)Math.Sqrt(n) - 2。这个差一位的问题我在调试时盯了很久才看出来。5.2 数组初始化与 GC 压力new bool[max 1]默认值是 false所以埃氏筛通常要再接一个Array.Fill(isPrime, true)。这相当于多遍历了一遍整个数组。如果 N10^8这个 Fill 本身也会花掉几百毫秒。想省这一步的办法是改变数组语义比如用合数标记命名默认 false 即是素数但代码可读性会下降。如果同一个方法会被频繁调用最好的做法是复用同一个数组而不是每次重新 new。每次 new 大数组都会给 GC 制造压力反复触发 full GC 后你会看到程序卡顿的时间比计算本身还长。在一段性能敏感的代码里对象池思想同样适用。还有一点把返回结果转成Listint或者int[]时ToArray/ToList 会再申请一遍内存把筛选出来的质数复制一份。如果外部调用只是需要逐个读取考虑返回 IEnumerable 配合 yield或者直接把 bool 数组的引用返回能省掉很大一笔分配成本。5.3 基准测试的经典误区我见过很多开发者在 Debug 模式下跑性能测试然后得出差距不大的结论。Debug 下 JIT 很多优化会被禁用结果就是慢的更快、快的更慢比率完全失真。我自己就吃过这个亏在 IDE 里点调试运行测出来只有几十倍差距还一度以为筛法不过如此。另外不要忽略 JIT 预热。 .NET 程序第一次执行某个方法时JIT 需要把 IL 编译为机器码这个时间可能比方法本身运行还长。如果你不预热直接测可能把 0.4ms 的筛法测成 200ms导致对比结果完全颠倒。规范的实验步骤是先让被测代码跑几轮进行预热再开始计时取多次结果的中位数而不是最小值或平均值。平均值容易被 GC 干扰最小值更接近真实计算能力。提示测试结束时打印总内存分配也很有用。你会发现一行 LINQ 版在 N10^6 时会分配数百 MB 的临时对象而埃氏筛几乎不分配额外内存。内存分配量有时比耗时更能说明问题。5.4 溢出与边界int 的暗坑这个坑值得单独拿出来说。埃氏筛的外层条件i * i max当 i 大于 46340 时i*i 就会超过 int 最大值 2147483647发生溢出变成负数循环条件瞬间失效。在 N10^7 时虽然内循环会跑 3162 次左右但因为 int 溢出可能让循环提前退出产出错误的素数表。解决方式很简单把 i 转换成 long 再求平方就像我前面代码里写的那样。我见过同事把(long)i * i写成(long)(i * i)这就完全失去意义了因为溢出已经发生转 long 只是在溢出之后补救。类似的边界问题还有素数表里忘记包含 0 和 1这两个数字既不是素数也不是合数必须显式处理。如果你用默认 false 表示素数那么索引 0 和 1 也要手动设置成 true 标记为非素数否则结果表里会错误地包含它们。最后再分享一点个人经验现在遇到枚举范围内所有素数的需求我会先问一句N 到底多大如果小于一万并且是临时验证脚本那用一行 LINQ 完全无所谓代码短、易读、够用。但如果 N 超过十万或者这段逻辑要被循环调用我直接上埃氏筛一步到位。而在选择埃氏筛还是欧拉筛时我觉得没必要太纠结。十万到一千万量级两者实测差距几乎看不出来上亿量级欧拉筛略占优但差距也就是常数级别。反而是跳过偶数和分段筛这类工程优化更容易带来数量级的收益。归根结底算法就是算法工程就是工程先选对复杂度再谈常数优化。