企业官网建设流程全解析

素数筛法这个经典问题，在 C# 里经常因为一行代码被引上热搜：求 [2,N] 之间的全部素数，可以用 LINQ 一行写完，也可以用十几行的埃氏筛。标题里说得更夸张——"1 行代码 vs 10 亿次计算，效率差 1000 倍？"我第一次看到这个说法是持怀疑态度的，毕竟 C# 再怎么说也是编译型语言，一行代码能慢到哪里去？直到自己搭了个基准测试环境跑了一遍，才对"算法复杂度"四个字有了刻骨铭心的认识。这篇我把自己跑出来的数据、几种写法的完整代码、以及后续优化中踩过的坑全部分享出来，尤其适合那些习惯有什么功能都先 LINQ 一把梭、又对性能敏感的同学。

1. 这个标题背后到底在比什么

1.1 两种思路的本质差异

先把问题限定清楚：我们要枚举 [2,N] 之间所有的素数。比如 N=100 万，要返回 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 迭代器。N=100 万时，这意味着系统要创建几十万个 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(); }

有两个边界细节容易写错。n=2 时 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。另一个细节是 n=4 时 sqrt=2，Range(2,1) 只包含数字 2，所以 4%2==0 会被正确筛掉。这一行代码里的每一个边界值都是踩过坑才确认的。

再看埃拉托斯特尼筛法：

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 更小的素数标记过了。比如 i=5 时，10、15、20 分别是 2 和 3 的倍数，早已被置为 false，完全没必要再走一遍。从 i*i 开始可以避免大量重复标记，是埃氏筛性能的重要来源。

之所以用 (long)i * i 而不是 i * i，是因为 int 乘法在 i 超过 46340 时就会溢出，变成负数导致条件判断失效。这个问题在 N 较大时非常隐蔽，后面避坑部分会再展开。

最后是欧拉筛，也叫线性筛：

public static List<int> GetPrimesLinear(int max) { var isComposite = new bool[max + 1]; var primes = new List<int>(); 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 再次标记。比如 i=6，p=2 时 v=12 被标记，随后 i%2==0 触发 break，p=3 就不会再去标记 18，因为 18 的最小质因子是 2，理应由 i=9、p=2 时来标记。这种精妙的控制让欧拉筛的理论复杂度来到 O(N)，虽然常数比埃氏筛略大，但扩展性更好。

2.3 实测数据：1000 倍真的存在

在我本机跑出的量级大致如下，不同配置机器会有浮动，但相对关系非常稳定：

这个表已经能回答标题里的问号：1000 倍不仅存在，在 N=10^7 这个量级只会更夸张。N=10^6 时 LINQ 版只跑到约 800 倍，是因为那个时候内层试除的平均次数还相对小，常数项占比高；随着 N 继续变大，渐近复杂度的差距会完全统治耗时，1000 倍是起步价。

3. 从复杂度推导看差距来源

3.1 时间复杂度：O(n√n) 与 O(n log log n)

为什么不满足于"跑出来是这么多"，而是要推导复杂度？因为只有理解了复杂度，你才能在任何 N 下预判性能，而不是依赖一次实验。

逐个试除法对每个整数 i 都要试除到 sqrt(i)，总操作量近似为：

∑(i=2..N) sqrt(i) ≈ (2/3) N^(3/2)

当 N=10^6 时，这个值大约是 6.7 亿次取模运算。标题里说的"10 亿次计算"就是这么来的——如果把取模、加法、迭代器移动都算进去，逼近 10 亿这个量级并不夸张。

埃氏筛则完全不同。对每个素数 p，它从 p² 开始标记 N/p 个倍数，总操作量约等于：

∑(p≤N) N/p ≈ N log log N

N=10^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 单独拎出来，之后只处理奇数。这样做数组长度直接减半，外层循环次数也减半，内存占用和运算次数双双下降。以 max=10^7 为例，布尔数组从 10 兆字节降到 5 兆字节，更容易装进 CPU 缓存。访问速度的提升比想象中明显。

一个常见的奇数化实现思路是把索引 i 映射到真实数 2*i+1。比如索引 1 对应 3，索引 2 对应 5。标记倍数时从 p² 开始，步长不是 p 而是 2p，因为偶数倍必然还是偶数，不需要管：

public static List<int> SieveOdd(int max) { if (max < 2) return new List<int>(); int half = (max - 1) / 2; var isPrime = new bool[half + 1]; Array.Fill(isPrime, true); var primes = new List<int> { 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：内存压缩到极致

如果你要跑 N=10^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)。这相当于多遍历了一遍整个数组。如果 N=10^8，这个 Fill 本身也会花掉几百毫秒。想省这一步的办法是改变数组语义，比如用"合数标记"命名，默认 false 即"是素数"，但代码可读性会下降。

如果同一个方法会被频繁调用，最好的做法是复用同一个数组，而不是每次重新 new。每次 new 大数组都会给 GC 制造压力，反复触发 full GC 后，你会看到程序卡顿的时间比计算本身还长。在一段性能敏感的代码里，对象池思想同样适用。

还有一点：把返回结果转成List<int>或者int[]时，ToArray/ToList 会再申请一遍内存，把筛选出来的质数复制一份。如果外部调用只是需要逐个读取，考虑返回 IEnumerable 配合 yield，或者直接把 bool 数组的引用返回，能省掉很大一笔分配成本。

5.3 基准测试的经典误区

我见过很多开发者在 Debug 模式下"跑性能测试"，然后得出差距不大的结论。Debug 下 JIT 很多优化会被禁用，结果就是"慢的更快、快的更慢"，比率完全失真。我自己就吃过这个亏：在 IDE 里点调试运行测出来只有几十倍差距，还一度以为筛法不过如此。

另外，不要忽略 JIT 预热。 .NET 程序第一次执行某个方法时，JIT 需要把 IL 编译为机器码，这个时间可能比方法本身运行还长。如果你不预热直接测，可能把 0.4ms 的筛法测成 200ms，导致对比结果完全颠倒。规范的实验步骤是：先让被测代码跑几轮进行预热，再开始计时，取多次结果的中位数而不是最小值或平均值。平均值容易被 GC 干扰，最小值更接近真实计算能力。

提示：测试结束时打印总内存分配也很有用。你会发现一行 LINQ 版在 N=10^6 时会分配数百 MB 的临时对象，而埃氏筛几乎不分配额外内存。内存分配量有时比耗时更能说明问题。

5.4 溢出与边界：int 的暗坑

这个坑值得单独拿出来说。埃氏筛的外层条件i * i <= max，当 i 大于 46340 时，i*i 就会超过 int 最大值 2147483647，发生溢出变成负数，循环条件瞬间失效。在 N=10^7 时虽然内循环会跑 3162 次左右，但因为 int 溢出可能让循环提前退出，产出错误的素数表。

解决方式很简单：把 i 转换成 long 再求平方，就像我前面代码里写的那样。我见过同事把(long)i * i写成(long)(i * i)，这就完全失去意义了，因为溢出已经发生，转 long 只是在溢出之后补救。

类似的边界问题还有素数表里忘记包含 0 和 1，这两个数字既不是素数也不是合数，必须显式处理。如果你用默认 false 表示素数，那么索引 0 和 1 也要手动设置成 true 标记为"非素数"，否则结果表里会错误地包含它们。

最后再分享一点个人经验

现在遇到"枚举范围内所有素数"的需求，我会先问一句：N 到底多大？如果小于一万，并且是临时验证脚本，那用一行 LINQ 完全无所谓，代码短、易读、够用。但如果 N 超过十万，或者这段逻辑要被循环调用，我直接上埃氏筛，一步到位。

而在选择埃氏筛还是欧拉筛时，我觉得没必要太纠结。十万到一千万量级，两者实测差距几乎看不出来；上亿量级欧拉筛略占优，但差距也就是常数级别。反而是"跳过偶数"和"分段筛"这类工程优化更容易带来数量级的收益。归根结底，算法就是算法，工程就是工程，先选对复杂度，再谈常数优化。