企业官网建设流程全解析

GESP五级C++语法里，“埃氏筛与线性筛”这一小块内容看着不大，却是很多同学从语法迈向算法思维的坎儿。你可能已经发现，五级考纲里关于枚举、模拟、基础数论的题目，不少都藏着筛法的影子——质数判断、区间素数统计、质因数分解，甚至某些计数题，本质都在考你能不能快速预处理一张“质数表”。这篇就以埃氏筛和线性筛为主线，把筛法的原理、模板、常见题型和考场上的注意事项一次性讲透，希望能给正在备考GESP五级的你一些实在的参考。

1. 筛法到底在解决什么问题

1.1 一个“查表”思维的入门

先从一个最朴素的问题说起：给定一个正整数 n，怎么判断 n 是不是质数？

第一反应肯定是枚举从 2 到 sqrt(n) 的所有整数，看 n 能不能被整除。单个判断还好，但如果是 10 万次判断，每次都要循环好几千遍，累计运算量轻松破亿，卡在超时里几乎没跑。这时候就需要换一种思路——不重复判断，而是提前把答案准备好，等真正要用的时候，直接查表。

筛法就是“批量生成质数表”的技术。埃氏筛（Eratosthenes筛法）和线性筛（欧拉筛）是其中两种最经典的实现，后者是前者的优化版。GESP五级虽然只要求掌握基础，但在课后习题里经常出现“1 ≤ n ≤ 10^6”这种数据范围，这时候只用暴力判断是扛不住的，必须用筛法预处理。

打个生活化的比方：你要在一堆纸牌里找出所有带红桃标记的牌，一张张翻当然也能做完，但如果你直接按花色把所有牌分开，再从中挑出红桃，效率就完全不一样了。筛法就是先整理好结构，再一次性把答案取出来。

1.2 埃氏筛的核心思想：标记法

埃氏筛的思路用一个字概括就是“标”。从小到大枚举每个数，如果一个数是质数，那么它的所有倍数一定不是质数，直接标记成合数。重复这个过程，剩下没被标记过的就是质数。

举个具体例子，比如筛到 n = 30：

• 2 是质数，把 4、6、8、10……30 全部标记合数；
• 3 是质数，但 6 已经被 2 标记过，从 9 开始继续标记：9、12、15……；
• 4 已经被标记，跳过；
• 5 是质数，从 25 开始标记（因为 10、15、20 已经被更小的质数标记过了）。

你会发现一个细节：当前质数 i 的倍数，不需要从 2i 开始标记，而是从 ii 开始标记。因为对于更小的倍数 ki（k < i），它一定已经被比 i 更小的质数筛掉了。这个优化虽然看起来只是把内层循环的起点往后挪了，但实际运行效率提升非常明显，在写代码时务必要用上。

埃氏筛的时间复杂度是 O(n log log n)，空间复杂度 O(n)。这个复杂度虽然已经很好，但唯一的问题是：一个合数可能被多个质因子重复标记多次。比如 30 会被 2、3、5 分别标记一次，虽然重复标记不影响正确性，但浪费了额外操作。如果数据范围继续增大到 10^7 以上，这种浪费就显得比较明显了。

1.3 线性筛的改进点：每个合数只筛一次

线性筛（欧拉筛）要解决的，正是埃氏筛“重复标记”的问题。它的核心原则只有一句话：每个合数只被它的最小质因子筛掉一次。

怎么做到？用两个数组配合：

• 一个数组记录每个数是否是质数；
• 另一个数组按顺序存下已经筛出的质数列表。

处理当前数 i 的时候，从小到大遍历已经筛出的质数 p，把 i * p 标记为合数。一旦 i 能被当前质数 p 整除，就立即 break，不再往后继续。

为什么这个 break 操作如此关键？因为如果 i 是 p 的倍数，那么对于后面更大的质数 q，i * q 的最小质因子仍然是 p，而不是 q。如果不 break，i * q 就会被当前这一轮错误地标记，后面轮到更大的数时它还可能被再标记一次，这样就破坏了“只筛一次”的原则。

举个具体的数：i = 6，prime 数组里是 [2, 3, 5]。先筛 6×2 = 12，标记合数；6 能被 2 整除，马上 break，不再筛 6×3 = 18、6×5 = 30。因为 18 = 2×9，它的最小质因子是 2，等 i = 9 时筛 9×2 = 18 才是它唯一该被筛掉的时机。正是这一行 break，让线性筛做到了 O(n)。

从实际做题角度说，五级阶段你要掌握的其实是两件事：第一，能在理解原理的基础上默写两种筛法；第二，能在题目里判断该用埃氏筛还是线性筛。很多同学一上来就背线性筛模板，看到 n = 10^6 就喜滋滋用线性筛，实际上用埃氏筛也完全能过，但如果不理解 break 的作用，代码写错了反而更麻烦。

2. 模板代码与逐行解析

2.1 埃氏筛标准模板

先给出我平时最常用的埃氏筛写法，简洁且不容易出错：

#include <iostream> #include <cstring> using namespace std; const int MAXN = 1000000; bool isPrime[MAXN + 1]; void eratosthenes(int n) { memset(isPrime, true, sizeof(isPrime)); isPrime[0] = isPrime[1] = false; for (int i = 2; i * i <= n; i++) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } }

几个关键点：

• memset把整个 isPrime 数组置为 true，再单独把 0 和 1 置为 false，因为这两个数既不是质数也不是合数。
• 外循环的终止条件是i * i <= n，不是i <= n。因为如果 i 是合数，它一定包含一个小于等于 sqrt(i) 的质因子，在之前就会被筛掉；而如果 i 是大于 sqrt(n) 的质数，它的平方已经超出范围，没有继续筛的必要。
• 内循环从i * i开始，这个起点优化上面已经解释过，背模板的时候尤其要留意别写成2 * i，否则虽然结果正确，但多了很多无效操作，当 n 达到 10^6 时差距还是看得见的。

2.2 线性筛标准模板

#include <iostream> #include <cstring> using namespace std; const int MAXN = 1000000; bool isPrime[MAXN + 1]; int primes[MAXN], cnt = 0; void linearSieve(int n) { memset(isPrime, true, sizeof(isPrime)); isPrime[0] = isPrime[1] = false; for (int i = 2; i <= n; i++) { if (isPrime[i]) { primes[cnt++] = i; } for (int j = 0; j < cnt && i * primes[j] <= n; j++) { isPrime[i * primes[j]] = false; if (i % primes[j] == 0) { break; } } } }

这个模板里有两层信息，你得真正看明白：

• primes数组的长度设为 MAXN，因为 n 以内的质数个数不会超过 n，所以这个大小是安全的。cnt 开始时为 0，每遇到一个质数就追加到数组尾部。
• 内层j < cnt的条件限制遍历范围，i * primes[j] <= n防止越界。每次把i * primes[j]标记成合数。然后是那句灵魂 break——if (i % primes[j] == 0) break;。

我在给某同学讲这段代码时发现一个常见的困惑：为什么在i * primes[j]已经被标记为合数后，才去判断 break？放在标记之前行不行？实际上，break 是在决定“是否要继续用后面的质数去乘当前 i”，它并不影响当前已经完成的标记操作，所以把它放在标记语句之后，逻辑是顺畅且直观的，不需要过度纠结顺序。

2.3 两个模板怎么选

直接给出我的建议：

• 如果 n ≤ 10^6，两种筛法都能过，建议用埃氏筛，代码更简单、变量更少，考场默写不容易出错。
• 如果 n ≥ 10^7，建议用线性筛。埃氏筛虽然也能跑，但重复标记的冗余操作会让常数变大，在时限比较紧的题目中风险更高。
• 如果题目特别强调“求每个数的最小质因子”或者需要额外维护某种信息，线性筛是更自然的扩展基础，因为在线性筛过程中你天然拥有质数列表和当前数 i，可以顺手记录很多附加信息。

还有一个细节：某些在线评测系统的内存限制很低，bool 数组本身占用较小，但如果你担心 memset 对大型 bool 数组的初始化开销，也可以直接用循环初始化或使用 bitset 类。不过 GESP 五级考试通常不会把这类性能问题作为卡点，重点还是代码正确。

3. 课后习题里的经典题型拆解

3.1 题型一：判断区间内质数的个数

这类题是筛法的“直接应用题”。题目描述通常长这样：给定正整数 L 和 R（比如 1 ≤ L ≤ R ≤ 10^6），求区间 [L, R] 中有多少个质数。

看到这种题，第一反应肯定不是逐个判断，而是先用埃氏筛或线性筛预处理出前缀质数数量，再 O(1) 回答每个询问。

具体做法是这样：

• 先筛出 isPrime 数组；
• 再用一个前缀计数数组 pre[i] 表示从 1 到 i 的质数个数，递推式是pre[i] = pre[i-1] + (isPrime[i] ? 1 : 0)；
• 查询区间时输出pre[R] - pre[L-1]。

这个做法背后藏着“前缀和”的思想，你甚至可以把它看成“把数据变成可查询的表”。考试时如果题目里给了多个区间询问，基本就是考察你有没有意识到预处理的价值。如果只给一个区间，那直接筛完扫一遍区间也行，但多个询问就一定要用前缀和。

我在某次模拟训练中看到某同学写了如下代码：

for (int i = L; i <= R; i++) { if (isPrime[i]) cnt++; }

这段逻辑本身没有大问题，但它把单个查询的复杂度做成了 O(R-L)，如果询问次数多了，整体就是 O(q × n)，很容易超时。筛完数组后多写一个前缀和数组，代码量增加不到三行，收益却截然不同。

3.2 题型二：质因数分解

GESP五级的课后习题里，质因数分解是另一个高频考点。给你一个整数 n，要求输出它的所有质因子及对应的指数。这类题在上一节筛法预处理之后，思路会变得非常清晰：

• 先用埃氏筛筛出 2 到 sqrt(n) 之间的所有质数；
• 从小到大遍历这些质数，如果 n 能整除它，就不断用这个质数除 n，同时记录次数；
• 循环结束后，如果 n 还大于 1，说明剩下这个数本身就是一个大于 sqrt(原n) 的质因子，直接输出。

这个方法背后是对“唯一分解定理”的运用。注意循环上界只需要到 sqrt(n)，因为任何合数 n 最多只有一个大于 sqrt(n) 的质因子，如果有，循环结束后它会作为剩余的部分自己暴露出来。

有个小坑要提醒：如果你直接对 n 的原值取 sqrt 作为上界，然后把 n 不断缩小，这个上界是不影响的，因为缩小后的 n 不可能出现新的、超出原始上界的因子。所以可以先int limit = sqrt(n) + 1;固定住上界，再去遍历质数。加 1 是为了避免浮点数精度误差导致漏掉临界情况，属于实战中养成的稳妥习惯。

3.3 题型三：结合计数思想的变式题

有些题目看起来和筛法关系不大，但本质上是在考察“基于质数表的计数能力”。比如：求 n 以内有多少个数恰好有 3 个正因子。

这种数的因子个数只有三种来源：平方质数 p^2，因为它的因子是 1、p、p^2。所以问题瞬间转化成：统计 n 以内有多少个质数 p，满足 p * p ≤ n。

如果你学会了筛法，这个题目就是先筛出质数表，然后遍历一遍质数数组，统计平方不超过 n 的个数。但如果真的一个一个判断质数，连质数表都没有，就会退化到暴力，数据一大就死。

这类变式题考的不是代码熟练度，而是你能不能把一个陌生问题“翻译”成筛法能解决的形式。刷题时见到这种题，别急着上手写代码，先在草稿纸上把数学关系理清楚，再想想它和筛法有什么关系。

4. 常见错误与考场调试心得

4.1 数组越界与初始化问题

每次提到筛法代码，我都要强调一遍：数组大小是 MAXN + 1，不是 MAXN。因为你要访问下标 n，而 C++ 数组下标从 0 开始，长度为 MAXN 的数组最大合法下标是 MAXN - 1。很多同学第一次写筛法，开的数组正好是 MAXN，结果访问 isPrime[n] 的时候就越界了。

越界不一定会立刻报错，在本地可能运行得好好的，一交到评测系统就出现 RE（运行时错误）或者莫名其妙拿到一个异常结果。这就是为什么我建议把数组长度都写成 MAXN + 1，并在代码开头用注释标明数据范围。

还有一个非常容易踩的初始化坑：memset(isPrime, true, sizeof(isPrime))这段代码看起来没问题，但如果你在全局区声明了 isPrime 数组，默认值本来就是 false，必须手动 memset 成 true 再单独处理 0 和 1。如果忘了把 0 和 1 置 false，后面查询 isPrime[0] 或 isPrime[1] 就会错误地返回 true，直接带崩整道题。

4.2 线性筛的 break 写错位置

线性筛里那句 break 是整个算法的精髓，也是错误的高发区。如果 break 写错了位置，比如写到了 if 外面，会导致某些合数被重复筛多次；如果 if 条件写反了，比如if (i % primes[j] != 0) break;，那就会漏筛，结果错得毫无规律。

防止这类错误最可靠的方法，不是靠记忆，而是拿一个具体的小数比如 i = 4、i = 6，手动模拟一遍代码流程。你只要在纸上走一遍 i = 6 的情况，就能理解为什么必须当 i % primes[j] == 0 的时候 break。经验之谈：考场时间再紧，也要先花十秒钟在草稿纸上推演一个测试用例，能省下后面调试的两个小时。

4.3 复杂度估算失误

埃氏筛的复杂度是 O(n log log n)，线性筛是 O(n)，看起来几乎没差别。但如果 n = 10^7，两者实际运行时间可能差出一倍多。原因在于埃氏筛有大量重复标记，每次访问数组还会产生缓存不命中的开销，常数比较大。

我见过某同学遇到 n = 10^7 的题，用埃氏筛交了三次都超时，改成线性筛一次就过了。所以在考试前，一定要对自己的代码在极端数据下的表现有概念：如果你能预判 n 的规模，就能选对筛法。

预估方法其实很简单，现场可以这样快速估算：普通 O(n log log n) 的埃氏筛，在 1 秒时限下大约能处理 2×10^7 左右的数据；线性筛大约能处理 5×10^7 以上。如果数据接近甚至超过这个量级，或者题目里有多个筛法场景，直接用线性筛，不要抱着侥幸心理。

4.4 用纸笔推演代替盲目调试

筛法调试最大的难点在于：数组里的内容不是肉眼能直观看到的，出错以后很难直接定位。我的建议是准备一张草稿纸，把 n 取到 20 左右，手动把两种筛法各走一遍，写下每一步标记了什么。不需要走完全程，走前几个数就能发现规律。

比如线性筛，用 i = 12 来推演：此时 primes 数组里已经存了 2、3、5、7、11。先筛 12×2 = 24，因为 12 % 2 == 0，break。所以 12 没有和 3、5、7、11 相乘。这个现象背后是：24 的最小质因子是 2，12×3 = 36 的最小质因子也是 2，要等到 i = 18 时筛 18×2 才轮到它。手动推演两三个这样的例子，比盯着代码看半天有效得多。

我在实际带同学刷题时还发现一个规律：如果某道题用线性筛结果输出偏多或偏少，九成原因都出在 break 的位置或者漏掉i * primes[j] <= n的条件判断，而不是思路错。检查的时候优先盯着这两处看，效率最高。

5. 备考GESP五级的实战建议

5.1 如何快速识别题目考点

看到题目就要快速判断它是不是筛法题，这是考场上争取时间的关键。一般来说，具备以下特征的题目，大概率是在考筛法：

• 数据范围大，n 轻松超过 10^5，暴力判断质数会超时；
• 题目需要多次质数判断，或者需要区间质数统计；
• 题干里出现“质因数分解”“因子个数”“约数和”“互质”等关键词；
• 解法需要预处理一张数表，再反复查询。

如果同时满足两条以上，直接启动筛法模板，不要犹豫。哪怕最后发现其实可以用其他数学办法更简单地解，筛法往往也不是错误方向，只是可能不是最优解。

还有一个细节值得注意：GESP五级考试里，筛法题目很少会直接问你“用筛法求质数”，而是把它包装成某个具体场景。比如模拟一个“质数接力”的游戏，或者给你一系列操作，问你经过某些步骤后剩下哪些数字。识别考点的能力，需要平时多见识一些包装过的题目，看到一句“把某个数标记为不可用”就能联想到筛法的标记过程。

5.2 代码模板的默写策略

考场上如果所有代码都临时想，时间一定不够。我的建议是：考前把埃氏筛和线性筛这两个模板压缩成自己能接受的最短版本，反复默写到形成肌肉记忆。

• 埃氏筛模板的核心是外循环 i 从 2 到 sqrt(n)，内循环 j 从 i*i 到 n，一旦看到if (isPrime[i])就进入标记循环。
• 线性筛模板的核心是 primes 数组、cnt 计数器、if (i % primes[j] == 0) break;这三件事。
• 两个模板都要特别写出isPrime[0] = isPrime[1] = false;，哪怕你已经默写了上百遍，下笔时还是要检查这一行。

默写模板不是死记硬背，而是要理解每一行的作用，否则换一个数据范围你就不敢改了。

5.3 个人实操后的体会

这套内容我带过不少准备GESP五级的学生，给我的感觉是：埃氏筛理解起来不难，真正拉开差距的是线性筛“为什么能 O(n)”这一步。很多同学上来就背代码，导致代码里带了一堆自己都没搞懂的条件，遇到细微改动就不知所措。

站在备考角度，我特别建议大家把这两道算法当成手推练习来做，而不是纯代码练习。拿一张白纸，从 n = 20 开始，用埃氏筛手算一遍标记过程，再用线性筛手算一遍，你会在过程中真正建立对“每个合数只被最小质因子筛掉一次”这句话的直观感受。

等这两个筛法真的过关了，你回头看五级里不少数论题都会变得简单——因为筛法不只是一个工具，更是一种“把重复计算变成预处理”的思维范式，这种范式在后续六级、七级的学习中还会反复用到。如果备考时间有限，先把这两个模板练到成肌肉记忆，比刷十道偏题怪题更有价值。