企业官网建设流程全解析

很多人一开始学筛法，都是在“埃氏筛”和“欧拉筛”之间来回纠结：两个都能找质数，代码也都只有十几行，凭什么说欧拉筛是“最优的方法”？严格回答这个问题之前，先明确这里说的找质数到底指什么，不是问某个数是不是质数，而是给定一个上限 n，把从 2 到 n 之间的所有质数全部找出来。这种批量场景下，欧拉筛（也叫线性筛）能做到每个合数只被筛掉一次，整体复杂度严格 O(n)，这也是它在众多筛法中被公认为最优的核心原因。这篇文章不讲空泛的理论，我会把欧拉筛从设计思路、代码细节、底层原理到实操坑点完整拆一遍，适合刚学到筛法、或者已经会用埃氏筛但想进一步理解线性筛精髓的开发者参考。

1. 从找质数的常规做法说起：埃氏筛到底慢在哪里

1.1 试除法判定质数的困境

最朴素的找质数思路是“逐个验证”。对范围里的每个数 x，去试除 2 到 √x 之间的所有整数，能整除就说明它是合数，否则就是质数。单次判断的时间复杂度是 O(√x)，看着还行，但放大到整个范围就不太对劲了：n 等于 10^6 时，总运算量大约是 n√n，也就是 10^9 量级，普通机器已经能感到明显卡顿；n 继续增大到 10^7，这个方案基本没法用。

有人会想到 Miller-Rabin 这种概率性判断方法来加速单次数判定，但要注意，找质数的下游任务往往不止“判断一次”，而是需要一份完整的质数表供后续使用。比如统计区间里每个数的最小质因子、计算欧拉函数、做莫比乌斯反演，这些都需要提前把 2 到 n 的所有质数“批量”准备好。一旦接受了这个前提，筛法就成了更自然的选择：生成一张表，以后所有操作都在表上直接查。

1.2 埃氏筛的原理和实现

埃氏筛的思路非常直白：从 2 开始，遇到一个质数 p，就把 p 的所有倍数标记为合数，剩下未被标记的就是质数。

const int MAXN = 1000000; bool is_prime[MAXN + 1]; void eratosthenes(int n) { memset(is_prime, true, sizeof(is_prime)); 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; } } }

注意一个优化点：内层循环从 ii 开始，而不是 2i。因为 i 的小倍数，比如 2i、3i 这些，一定已经被更小的质因数标记过了，从 i*i 继续能省掉重复工作。

埃氏筛的时间复杂度是 O(n log log n)，对绝大多数场景已经足够快，而且实现简单、缓存友好，这也是很多教科书把它作为入门筛法的原因。

1.3 重复标记：埃氏筛的核心痛点

埃氏筛有个“看不见的浪费”：同一个合数会被多次重复标记。以 12 为例，当 p=2 时，12 作为 2 的倍数被标记一次；当 p=3 时，12 又作为 3 的倍数再被标记一次。再比如 30，它同时能被 2、3、5 整除，在埃氏筛里至少要被标记三次。

单看每次标记，确实只是给 bool 数组赋个值，成本非常低。但 n 一旦到 10^7、10^8 量级，这种重复标记的累积开销就很可观了。更重要的是，埃氏筛的思维模式是“质数主动筛掉自己的倍数”，它完全没考虑“每个合数到底应该由谁负责”。如果能让每个合数有且只有一个固定的筛除来源，复杂度就能从 O(n log log n) 严格压到 O(n)，这正好是欧拉筛要做的。

2. 欧拉筛的设计思路：让每个合数只被筛一次

2.1 最小质因数：整个算法的支点

每个合数都有一个唯一确定的属性：最小质因数，也叫最小质因子。比如 12 = 2 × 2 × 3，最小质因子是 2；45 = 3 × 3 × 5，最小质因子是 3；77 = 7 × 11，最小质因子是 7。

“唯一确定”这四个字就是欧拉筛的突破口。因为质因数分解在数学意义上只有一种拆法，所以“这个合数的最小质因子是谁”这个问题有且只有一个答案。欧拉筛的全部设计目标可以浓缩成一句话：让每个合数，恰好只被它自己的最小质因子筛掉。

这个目标听起来简单，真正做起来却要小心设计流程。一个合数 x 可能有多个质因子，怎么保证扫描途中只有“最小的那一个”真正动手标记 x，其他质因子路过时直接跳过？这需要一个简单、可编码、又能从原理上杜绝重复的规则，也就是后面要重点讲的 break 条件。

2.2 欧拉筛的宏观流程

欧拉筛和埃氏筛的视角完全不同。埃氏筛是“质数主动找自己的倍数”，欧拉筛是“外层数 i 和质数列表里的质数逐一配对，生成合数 i × primes[j]”，同时通过一个整除判断保证每个合数只被最小质因子筛掉。宏观流程如下：

• 初始一个空数组 primes 存放已经找到的质数，一个 bool 数组标记合数；
• 从 2 遍历到 n，如果当前 i 没有被标记为合数，说明它是质数，加入 primes；
• 内层循环让 i 依次乘以 primes 里的质数，得到合数 i × primes[j]，标记为合数；
• 关键一步：一旦发现 i 能被当前质数 primes[j] 整除，就立即退出内层循环。

这里最后一步就是欧拉筛和埃氏筛最本质的区别，它决定了后续更大的质数不会再来参与这一轮的筛选。

我第一次学欧拉筛时，代码倒是能背下来，但完全想不明白为什么要 break。直到我手动模拟了 2 到 20 的完整筛选过程，才真正领会到断行的作用。建议所有刚接触的人先别急着看证明，先跟着第 3 节手算一遍流程，很多疑惑会自然解开。

2.3 与埃氏筛的宏观对比

这张表里我只给出结论，后面的章节会详细解释复杂度推导和扩展用法。先说结论是为了让读者心里有个底：欧拉筛看似只解决“找质数”的问题，但它真正的价值在于把合数和最小质因子建立了稳定的绑定关系，这种绑定是后续一系列数论预处理的根基。

3. 欧拉筛代码实现与逐行拆解

3.1 基础版本代码（C++）

#include <bits/stdc++.h> using namespace std; const int MAXN = 10000000; bool is_comp[MAXN + 1]; // false 表示未被标记为合数，即质数 vector<int> primes; void euler_sieve(int n) { for (int i = 2; i <= n; i++) { if (!is_comp[i]) { primes.push_back(i); } for (int j = 0; j < (int)primes.size(); j++) { long long v = 1LL * i * primes[j]; if (v > n) break; is_comp[v] = true; if (i % primes[j] == 0) break; } } }

这个版本里我特意用了is_comp而不是is_prime。虽然两种写法都能跑，但语义上完全不同：is_comp表达的是“这个数是否被标记为合数”，更符合欧拉筛的实际运作方式。如果你心里一直想着“is_prime 默认全 true，筛掉就变 false”，在排查问题的时候特别容易绕晕。

3.2 代码各部分的设计考量

逐个解释几个看起来不起眼、但特别容易出问题的细节。

数组大小为什么是MAXN + 1。因为我们访问的下标从 2 到 n，如果数组只开MAXN，访问is_comp[MAXN]就会越界。竞赛题里 n 经常作为输入参数，更稳妥的做法是用动态数组或vector<char>按实际 n 申请空间。

乘积v为什么用long long。i最大能到 n，primes[j]也可能很接近 n，两者相乘很容易超出 32 位int范围。例如 n = 10^7 时，i 和 primes[j] 的乘积可以达到 10^14，直接乘会溢出，结果变成负数或者错误值。用1LL * i * primes[j]先转换成 64 位整数，再与 n 比较，才是安全的。这一步看着蠢，但真正出过事的同学都知道这个坑有多深。

为什么先判断v > n再标记。如果乘积超出 n，直接访问is_comp[v]就会数组越界。这个判断顺序必须放在赋值is_comp[v] = true之前，很多人写反，一运行就崩。

为什么j < (int)primes.size()。size()返回的是无符号类型，如果直接和带符号的j比较，编译器会做隐式转换，某些边界场景下会出现意外行为。虽然这里影响不大，但写成强制转换是更严谨的习惯。

3.3 手算推演：前几轮循环到底发生了什么

我把前几轮完整列出来，这一节值得反复看：

• i=2：is_comp[2] 为 false，加入 primes，现在 primes=[2]。内层 j=0，v=2×2=4，标记 is_comp[4]=true，然后 2%2==0，break。
• i=3：is_comp[3] 为 false，加入 primes，现在 primes=[2,3]。内层 j=0，v=6，标记 is_comp[6]=true，3%2!=0，继续；j=1，v=9，标记 is_comp[9]=true，3%3==0，break。
• i=4：is_comp[4] 已经是 true，不加入 primes。内层 j=0，v=8，标记 is_comp[8]=true，4%2==0，break。注意这里没有用质数 3 去生成 12，因为 12 的最小质因子是 2，应该留给 i=6 时再用 2 来筛。
• i=5：is_comp[5] 为 false，加入 primes，现在 primes=[2,3,5]。内层依次算 10、15、25，分别标记，5%5==0 时 break。
• i=6：is_comp[6] 为 true，不加入 primes。内层 j=0，v=12，标记 is_comp[12]=true，6%2==0，break。

看到 12 的筛选来源了吗？它在 i=6、p=2 这一轮被标记，而不是在 i=4、p=3 那一轮。这正是 break 条件在起作用：当 i=4 时，因为 4 能被质数 2 整除，内层循环在碰到质数 3 之前就已经强制退出，所以 12 永远轮不到 3 来筛。这个机制保证了每个合数只被最小质因子筛掉，而且不会漏掉任何一个。

3.4 顺手给一个 Python 版本

def euler_sieve(n): is_comp = [False] * (n + 1) primes = [] for i in range(2, n + 1): if not is_comp[i]: primes.append(i) for p in primes: v = i * p if v > n: break is_comp[v] = True if i % p == 0: break return primes

Python 版本不需要考虑整数溢出，逻辑和 C++ 完全一致。实际跑的话，Python 到 n=10^7 已经明显吃力，瓶颈主要在解释器循环开销，不是算法本身。如果要大规模使用，建议还是用 C++、Rust 之类编译型语言，或者用 Python 只做小范围的验证和教学。

4. 那个关键的 break：欧拉筛的灵魂所在

4.1 为什么 break 能保证不重不漏

先证明“不漏”：任意一个合数 x，把它写成 x = p × m，其中 p 是 x 的最小质因子。当外层循环遍历到 i = m 时，因为所有小于等于 m 的质数都已经提前被收集进 primes 列表，所以在遍历质数列表的过程中，一定能遇到 p 这一项。在遇到 p 之前的那些比 p 更小的质数 q，不可能整除 m，否则 q 也必然是 x 的质因子，这和“p 是最小质因子”直接矛盾。所以内层循环不会提前 break，一定能在 j 走到 p 的位置时计算出 v = m × p = x，并且 x ≤ n，于是 x 被标记。这说明所有合数都会被筛到。

再证明“不重”：假设某个合数 x 被标记了两次，说明存在两轮不同的筛选来源 (i₁, p₁) 和 (i₂, p₂)，满足 i₁ × p₁ = i₂ × p₂ = x，并且 p₁、p₂ 都是质数。不妨设 p₁ < p₂，那么 i₁ = x/p₁ > i₂ = x/p₂。考虑外层循环到较小的 i₂ 那一轮，因为 p₁ < p₂，质数列表从 2 开始遍历，循环会先遇到 p₁。此时由于 x = i₂ × p₂，而 p₁ 整除 x，且 p₁ 和 p₂ 是不同的质数，所以 p₁ 必然整除 i₂。于是当循环走到 p₁ 时，条件i₂ % p₁ == 0成立，内层循环立刻 break，根本走不到 p₂。所以 p₂ 永远没有机会去筛掉 x。矛盾。

把这两点翻译成人话就是：每个合数都有且仅有一次被筛的机会，而且这次机会被牢牢锁定在最小质因子那一轮。其他质因子看着好像也能筛它，但都会被 break 挡在门外。

4.2 去掉 break 会发生什么

我见过不少人学欧拉筛时为了省事，直接把if (i % primes[j] == 0) break;这一行删掉，美其名曰“反正也能筛出所有合数”。从结果看确实没错，标记出来的合数集合和原来完全一致，但过程完全退化：每个 i 都会和 primes 列表里所有乘积不超过 n 的质数配对，同一个合数会被不同的 (i, p) 组合反复标记很多次。

还是拿 12 举例，去掉 break 后，它既会在 i=6、p=2 这一轮被标记，又会在 i=4、p=3 这一轮被标记。15 也是一样，既在 i=5、p=3 时被筛，又在 i=3、p=5 时被筛。合数的重复标记次数和它的质因子个数有关，整体复杂度从 O(n) 退化到和埃氏筛相近甚至更差的水平。换句话说，欧拉筛最重要的价值就在这一行 break 里，删掉它，剩下的只是“一个写起来更麻烦的埃氏筛”。

5. 复杂度分析、性能实测与语言差异

5.1 时间复杂度的直观理解

为什么欧拉筛是 O(n)？核心论据是：内层循环里每次迭代，要么成功标记一个新的合数，要么因为i % primes[j] == 0或者v > n触发 break 退出。而每个合数只会被标记恰好一次，所以标记操作的总次数不超过 n。break 操作每个外层 i 最多发生一次，所以 break 的总次数不超过 n。二者合计，内层循环的总执行次数是 O(n) 级别，加上外层循环 n 次，总时间复杂度就是严格的 O(n)。

这个推导最关键的地方在于“每个合数只被标记一次”这个结论，它是由第 4 节的正确性证明保证的。换句话说，复杂度分析和正确性分析其实是同一件事。

5.2 实际运行表现和埃氏筛差多少

理论归理论，实际跑起来还要考虑常数。埃氏筛的 O(n log log n) 增长非常缓慢，n=10^9 时 log log n 大约也就 3 左右，所以两者理论复杂度只差一个很小的增长因子。而欧拉筛多了取模运算i % primes[j]，取模在 CPU 指令层面比简单的数组赋值贵不少，因此在我自己平时的基准测试和一些竞赛选手分享的数据里，n 在 10^7 量级时，欧拉筛和优化过的埃氏筛实际差距并不像理论看起来那么大，某些时候甚至更慢。

这张表是数量级上的参考，具体数值受编译器优化、CPU 缓存、实现细节影响很大。我要强调一个反直觉的结论：如果你只是想让代码跑得快，纯粹找质数的话，优化过的埃氏筛在某些环境下反而更快；欧拉筛真正的优势不是“常数更小”，而是“每个合数只处理一次”这个结构性优势，它让我们可以顺便统计出大量额外信息，这才算真正的“最优方法”。

5.3 不同语言的实现注意事项

C++ 里优先使用bool数组或者vector<char>，慎用vector<bool>。vector<bool>节省内存但读写有额外位运算开销，访问大量下标时会比普通bool数组慢不少。当然如果 n 大到上亿，内存紧张，vector<bool>的优势就很明显，这时候需要在速度和内存之间做取舍。

Python 中要注意primes的遍历方式。比如for p in primes比带下标访问primes[j]更简洁，性能相差不大。对于教学和验证完全可以接受，真正大批量计算时建议考虑numpy优化的埃氏筛变体，而不是硬用纯 Python 跑欧拉筛。

另外提醒一个细节：无论什么语言，都要保证临时数组在多次调用函数时不会残留上一次的数据。C++ 里局部数组最好手动fill初始化，全局数组也建议每次调用前重置，否则多次调用之间相互污染，排查起来特别恶心。

6. 常见错误、坑点与调试技巧

6.1 最常见的几种错误

第一类错误是边界处理。数组下标从 0 到 n，容易忘记处理 n 本身；用全局固定大小数组时，没有检查输入 n 是否超过数组上限，运行到一半越界崩溃。

第二类错误是 break 条件写反。把i % primes[j] == 0写成primes[j] % i == 0，数学含义完全变了，结果就是筛出来的列表缺漏一大堆质数。这种错误最难查，因为算法逻辑看起来好像没变，实际上完全不是一回事。

第三类错误是乘积溢出。32 位int相乘，n 超过 46340 左右就可能溢出，如果直接把乘出来的怪值当成数组下标，轻则结果错误，重则直接段错误。

第四类错误是删掉 break 条件。前面说过了，这会让算法退化，但很多时候从结果上根本看不出来，排查时特别容易忽略。如果你觉得某个“欧拉筛”跑得比预期慢很多，先去检查是不是 break 少写了。

6.2 快速自检与调试方法

最直接的方法是拿小 n 做手算对照。比如 n 取 30，正确的质数列表是 2、3、5、7、11、13、17、19、23、29。把代码跑一遍，比对一下就知道有没有漏筛。

第二个方法是把“每个合数的筛除来源”打出来。改造代码，维护一个by[v]数组，记录合数 v 是被哪个质数筛掉的，最后检查一下所有合数的by[v]是否恰好等于它的最小质因子。如果能做到，说明 break 逻辑完全正确。我把这一步称为“可视化验证”，它对理解欧拉筛极其有效。

第三个方法是统计标记次数。因为每个合数只被筛一次，理论上标记操作的次数应该等于 n 以内的合数个数，也就是 n - 1 - primes.size()。如果统计到的标记次数明显大于这个值，几乎可以确定是 break 条件丢了或者写错了。

6.3 性能优化的小技巧

编译时开-O2或-O3，优化效果非常明显。如果 n 特别大，换成bitset来存储合数标记，内存占用能压缩到原来的八分之一，访问速度也不会差太多。EXUM：如果你在竞赛环境下，复杂度要求极高，可以用bitset配合埃氏筛思想，在某些实现里甚至比欧拉筛更快。

还要记住：欧拉筛的内层循环里，i % primes[j]这个取模运算虽然准确，但并不是完全没有优化空间。如果后续你只关心最小质因子，可以在维护minp数组的同时，用它来加快判断，不过这是进阶话题了，初学者不需要纠结。

7. 欧拉筛的扩展：从一个筛子到一个工具箱

7.1 顺便得到最小质因子数组

因为每个合数 v 都是在“最小质因子 primes[j]”这一轮被标记的，所以我们在标记的同时顺手记录一下即可：

int minp[MAXN + 1]; // 内层循环里加一行 is_comp[v] = true; minp[v] = primes[j]; // 这个 primes[j] 就是 v 的最小质因子

这个minp数组在质因数分解里有大用途。拿到一个数 x，直接读minp[x]得到它的最小质因子，然后不断除下去，就能在 O(log x) 时间里完成分解。对于后面要算约数个数、约数和等问题，这几乎是标准前置步骤。

7.2 用同一套流程求欧拉函数

欧拉函数 φ(n) 表示 1 到 n 之间与 n 互质的整数个数，是数论题里出现频率最高的函数之一。它满足积性：当 a 和 b 互质时，φ(a×b) = φ(a) × φ(b)。结合欧拉筛的筛选顺序，我们可以在筛质数的同时递推出每个数的 φ 值：

• 如果 i 是质数，则 φ(i) = i - 1；
• 用质数 p 筛掉 v = i × p 时：
  • 如果 i % p != 0，说明 p 和 i 互质，φ(v) = φ(i) × (p - 1)；
  • 如果 i % p == 0，说明 p 已经出现在 i 的质因数里，φ(v) = φ(i) × p。

有了这两条规则，代码只需要在欧拉筛内层循环里加几行：

vector<int> phi(n + 1, 0); phi[1] = 1; for (int i = 2; i <= n; i++) { if (!is_comp[i]) { primes.push_back(i); phi[i] = i - 1; } for (int j = 0; j < (int)primes.size(); j++) { long long v = 1LL * i * primes[j]; if (v > n) break; is_comp[v] = true; int p = primes[j]; if (i % p == 0) { phi[v] = phi[i] * p; break; } else { phi[v] = phi[i] * (p - 1); } } }

注意这里当i % p == 0时必须 break，这不仅是为保证欧拉筛复杂度，同时保证了v的最小质因子就是 p，递推公式才能成立。

7.3 扩展到莫比乌斯函数

莫比乌斯函数 μ(n) 是另一个积性函数，定义比较特别：μ(1) = 1；如果 n 有平方因子，μ(n) = 0；如果 n 是 k 个不同质因子的乘积，μ(n) = (-1)^k。用欧拉筛递推也很简单：

• 质数 p 的 μ(p) = -1；
• 如果 i % p == 0，说明 i × p 含有平方因子 p²，μ(i × p) = 0；
• 否则 μ(i × p) = -μ(i)。

一样的循环，不一样的几行代码，欧拉筛这个“骨架”就可以同时维护出质数表、最小质因子、欧拉函数、莫比乌斯函数。这才是它被称为“线性筛”的完整意义——它不只是一个算法，而是一整套数论预处理的模板框架。

7.4 什么时候不推荐用欧拉筛

最后泼一盆冷水。如果你的目标真的只是“找质数”，而且 n 在几百万到几千万量级，优化过的埃氏筛往往更简单、更省事，甚至更快。欧拉筛的优势体现在需要额外信息的场景，比如求最小质因子、欧拉函数、莫比乌斯函数，或者在线性时间内完成多项数论预处理。所以选型时不要只看“谁的理论复杂度低”，还要看你的下游任务到底是什么。工具选不对，最优方法也会变成多余方法。

我自己在竞赛和工程里用了很多年欧拉筛，最大的体会是：它把“每个合数绑到最小质因子上”这个抽象概念，变成了一行可以背下来的 break，又因为这一行 break，让很多数论信息都能顺手线性求出。建议你把核心模板背熟，同时把第 4.1 节那种不重不漏的直觉刻在脑子里。等哪天遇到“线性时间内预处理一堆积性函数”的需求，你会发现今天花在这篇文章上的时间完全值回来了。