企业官网建设流程全解析

GESP C++五级考试里，很多考生觉得“语法知识”嘛，就是背一背数据类型、循环、数组、函数就够了。但真到考场你会发现，那些和数学沾边的算法题，才是最容易拉开差距的地方。埃氏筛和线性筛就是典型代表，表面上是“筛质数”，骨子里其实在考你对数组下标、循环边界、复杂度控制这些基本功的掌握程度。

这篇文章我打算把这两个筛法完整拆开讲，从原理、代码、复杂度一直到考场上的实用技巧都过一遍，包括我这些年帮人调代码时踩过的一些坑。无论你是正在备五级，还是只想把筛法彻底弄明白，这篇都值得静下心来看完。

1. 为什么五级考点会考到筛法

1.1 筛法在语法知识里扮演什么角色

如果你翻过五级考试的大纲，会发现它并不强调高级算法，更多是考察C++里循环嵌套、数组操作、函数封装这些语法能力的综合运用。而筛法恰好是一个能把它们全部串起来的经典话题：你需要用一个数组存状态，用循环遍历下标，用边界条件控制范围，还要用函数把步骤封装清楚。

我见过不少学生，单独讲for循环、一维数组都听得很明白，一写筛法就漏写条件、越界访问。原因不是语法不会，而是没有把语法用“解决问题”的方式组织起来。筛法看起来就是几行代码，但它逼着你想清楚：为什么这个循环要这样写？为什么那个条件不能少？这些思考过程恰恰是五级考试真正想考察的能力。

另外，素数相关题目在等级考试里属于常客。给定一个范围，让求质数个数、求某个区间内的质数，或者拿质数表做后续某个判断，这类题一旦遇到，筛法就是最直接的预处理手段。要是连筛法都没掌握，你临时用暴力去试，范围稍大一点就可能超时。

1.2 和暴力判断相比，筛法强在哪

先看最笨的办法：对每个数x，判断它是不是质数。判断单个数要跑根号x次，全部数加起来的复杂度大概是O(n√n)。n只有1000、10000的时候还没什么感觉，一旦n到100万，计算次数就上亿了，考试时限根本顶不住。

筛法是反过来想的：不求每个数“是不是质数”，而是先把已知质数的倍数全部划掉。这样一趟预处理下来，所有小于等于n的数是不是质数就全知道了。埃氏筛复杂度约O(n log log n)，线性筛更是稳定在O(n)，都比暴力快一个量级。而且筛完以后的查询是O(1)的，后面再怎么用都方便。

所以说，筛法不只是一个“模板”，它是很多数论题的地基。你把这个地基打牢了，后面再遇到带质数限制的题目，至少不会被预处理卡住。

2. 埃氏筛：原理与实现细节

2.1 从“划掉倍数”到 i*i 优化

埃氏筛的核心逻辑特别直观：从小到大扫描，遇到没被划掉的数就认定它是质数，然后把它所有的倍数全部划掉。比如2是质数，就划掉4、6、8、10……；接着3没被划掉，那3也是质数，再划掉9、12、15……；到了4，它已经被2划掉了，直接跳过。

这里面有两个非常关键的优化，考试里写错了不一定报错，但会白白浪费时间，属于典型的“逻辑正确但性能差点”。

第一个优化是内层从ii开始划，而不是从2i开始。原因很简单：一个合数ki，如果k小于i，那它早就被更小的质因子标记过了。比如处理到质数5时，5×2=10已经被2划掉，5×3=15已经被3划掉，5×4=20也已经被2划掉了。真正需要通过5来划掉的，至少是5×5=25。所以从ii开始既不会漏，也能减少大量重复的赋值操作。

第二个优化是外层循环只到√n就停。你想，如果n是合数，那它一定有一个因子不超过√n。既然所有涉及小因子的合数都已经在小因子那轮被划掉了，那超过√n的大因子对应的合数自然早就被标记过了，不需要再继续跑。

2.2 一段可以直接上考场的埃氏筛

直接给一段我比较常用的写法：

#include <bits/stdc++.h> using namespace std; const int MAXN = 1000000; vector<bool> isPrime(MAXN + 1, true); void eratosthenes(int n) { isPrime[0] = isPrime[1] = false; for (int i = 2; i <= n / i; ++i) { if (!isPrime[i]) continue; for (long long j = 1LL * i * i; j <= n; j += i) { isPrime[j] = false; } } }

这里有几个细节我特意处理过。外层判断我用了i <= n / i，而不是i * i <= n。两者数学上等价，但前者不会出现整型乘法溢出的问题。如果你把n开得比较大，比如接近2×10^9，i*i写成int会直接炸掉，写成i <= n / i就完全没有这个隐患。

内层循环我把j定义成long long，同时用1LL * i * i做初始化。这样即使n比较大，也不会因为乘法溢出导致负下标、死循环这类诡异故障。考试时候n开到10^6、10^7这个量级很常见，这点防御性写法能帮你少踩很多坑。

2.3 埃氏筛的复杂度为什么是 O(n log log n)

很多人对这个复杂度不明白，背下来也心虚。其实不用把它想得太复杂。外层每遇到一个质数p，内层会标记n/p个数。对所有不超过n的质数求和，也就是n乘以一个关于质数倒数的和。这个和的量级大约是ln ln n，所以总复杂度就是O(n log log n)。

在实际赛题数据下，这个复杂度已经非常够用。n为10^6时，埃氏筛通常几十毫秒内就能跑完；n到10^7也还在可接受范围内。更极端的情况才需要考虑线性筛或进一步优化。

所以如果你参加五级考试，说明考试范围通常不会给你一个n=10^8还要反复跑筛法的题。埃氏筛代码短、思维量小、不容易写错，对考试来说已经是很稳的选择。

3. 线性筛：让每个合数只被筛一次

3.1 核心思想与那个关键的 break

埃氏筛有个小毛病：一个合数可能会被多个质数重复标记。比如12，会被2划掉一次，又会3划掉一次。数据量小的时候无伤大雅，但数据量一上来，那些重复操作就会拖慢速度。

线性筛的思路是：让每个合数只被它的最小质因子筛掉。这样每个合数在算法运行期间只会被标记一次，整体复杂度就严格控制在O(n)。

实现上靠的是这一段：

if (i % primes[j] == 0) break;

这行代码是整个线性筛的灵魂。它的意思是：当发现primes[j]已经是i的质因子时，就停掉当前这轮内层循环。为什么？因为后面的i * primes[k]（其中k > j）虽然也是合数，但这个合数的最小质因子其实是primes[j]，不是primes[k]。如果现在继续标记，将来还会被primes[j]再标记一次，等于白做了重复功，破坏了“只筛一次”的原则。

举个例子。处理到i=4时，质数表里有2、3。先用2做标记：4×2=8，标记没问题；再看4%2==0，于是break，不处理4×3=12。等到i=6时，6%2也等于0，标记完6×2=12后break。你看，12最终只被标记了一次，而且是被它的最小质因子2标记的。

3.2 完整代码与考场注意事项

线性筛的标准套路如下：

#include <bits/stdc++.h> using namespace std; const int MAXN = 1000000; int primes[MAXN + 5], cnt; bool composite[MAXN + 5]; void linear_sieve(int n) { for (int i = 2; i <= n; ++i) { if (!composite[i]) { primes[cnt++] = i; } for (int j = 0; j < cnt && 1LL * i * primes[j] <= n; ++j) { composite[i * primes[j]] = true; if (i % primes[j] == 0) break; } } }

写这段代码时有几个点特别容易出错。

第一，条件顺序不能乱。i * primes[j]要先判是否超过n，再执行标记。如果不判，数组可能越界；如果判得太后，可能已经访问了不存在的下标。第二，if (i % primes[j] == 0) break;必须放在标记之后，不能提前。一旦提前，会漏掉一个本来应该标记的合数。第三，复合数标记数组建议用bool或vector<char>，不要图省事直接用vector<bool>以外的奇怪类型。

primes数组的容量按照n来开就够，实际质数个数远小于n，开大一点只是多占点内存，不会有问题。我习惯开成n+5，既保险又不用记精确公式。

3.3 线性筛为什么有额外价值

线性筛的价值远不止筛质数。因为它通过“最小质因子”控制每个合数恰好被筛一次，你在筛的过程中可以顺带维护很多数论函数，比如欧拉函数、莫比乌斯函数、约数个数等等。

这个特点在学校竞赛或者更高级别的考试里非常常用。比如想求一个范围内所有数的欧拉函数，普通写法可能要对每个数分解质因数，很慢。但线性筛可以在遍历每个数时顺势更新对应函数，总复杂度依然是O(n)。

我在带学生的时候经常说：如果只为过五级，线性筛可以当作储备知识；但如果想继续往六级、七级走，或者以后参加信息学类的比赛，线性筛的这层扩展能力迟早会用到。所以现在学的时候多理解一层，后面会省很多事。

4. 实操：把筛法接到真实题目里

4.1 从“求质数列表”到完整解题流程

很多同学备考时只会背筛选代码，一上考场遇到完整题目还是懵。其实筛法类题目的解题思路很固定，基本是三步走。

第一步，看清楚题目要的是“一次预处理查询多次”，还是“只查一个数”。如果是前者，直接筛。第二步，确定数据范围，选择用埃氏筛还是线性筛。第三步，筛完后按题目要求统计或输出。

比如一道很典型的题：输入n，输出1到n之间所有质数的个数。解题流程就是先调一次筛子，把isPrime表处理完，然后从2到n扫一遍做计数。有些学生喜欢在筛完的循环里顺手统计，这没问题，但要注意别把“预处理函数”和“统计逻辑”混在一起，否则后面排查bug时会很痛苦。

我建议在考试时把筛法封装成一个函数，然后在main里单独维护统计逻辑。这样逻辑分层清楚，出错了也知道去哪个部分找。这个习惯看着普通，实际考试里非常救命。

4.2 区间筛套路，考试里的高发点

还有一种题目，n的范围特别大，比如给一个区间[L,R]，L和R能到10^12，但区间长度只有10^5甚至更小。这时候你不可能开一个R大小的数组，内存早就爆了。正确做法是区间筛。

思路是这样的：先用普通筛法把不超过√R的所有小质数筛出来，然后拿这些小质数去标记大区间[L,R]里对应的合数。因为区间长度不大，用一个偏移数组就够了。

核心代码可以这样写：

vector<bool> segment(R - L + 1, true); if (L == 1) segment[0] = false; for (int i = 2; i * i <= R; ++i) { if (!isPrime[i]) continue; long long start = max(1LL * i * i, ((L + i - 1) / i) * 1LL * i); for (long long x = start; x <= R; x += i) { segment[x - L] = false; } }

这里的start计算是重点。((L + i - 1) / i) * i是大于等于L的最小的i的倍数，也就是标记起点。但起点还要和i*i取最大值，避免重复标记已经被更小质数处理过的位置。这个公式看起来繁琐，其实就是“向上取整到i的倍数”。理解了这一点，代码就很好记。

五级虽说未必直接考区间筛，但掌握了它，你对数组偏移和边界处理的理解会明显上档次。

4.3 两种筛法在实际运行中的表现对比

我给一个参考性的对比表，方便你心里有数：

很多人误以为线性筛一定比埃氏筛快很多，其实不一定。线性筛为了追求“每个合数只标记一次”，多做了很多取模和压栈式判断，常数并不小。在小数据范围下，两者实测时间往往差别不大，甚至埃氏筛因为代码更简单，编译优化后反而可能更快一点。

所以考试取舍很简单：只求质数，写埃氏筛；要顺便算数论函数，再上线性筛。别为了炫技去用复杂方案，考场里“写得出来”比“理论上更快”重要得多。

5. 常见问题与排查技巧实录

5.1 那些高频翻车点

我帮人改过很多筛法代码，最常见的翻车点就那么几个，今天一次性列出来。

一是下标越界。很多人在内层循环用j <= n当边界，但j的初始值是i*i，如果i比较大，j很容易超过数组上界。尤其当你用int j且n超过10^6时，i*i的乘法结果可能溢出成负数，负下标访问会让程序直接崩溃。

二是边界状态没处理。isPrime[0]和isPrime[1]必须手动设为false。很多人从模板里抄代码，抄完连这两行初始化都漏了，导致0和1在输出阶段全被当成质数，结果自然全错。

三是线性筛break时机不对。写给if (i % primes[j] == 0) continue;，这一字之差会让循环继续跑，破坏线性性质，虽然小数据下可能看不出问题，但大数时会有重复标记。

四是vector<bool>的使用误区。vector<bool>是位压缩版本，节省空间，但它的操作效率和普通bool数组不太一样。想偷懒时可以直接用vector<char>，至少不会因为某些引用问题导致意外调试困难。

5.2 本地调试时的实操技巧

筛法代码出问题时不报错是最烦人的，大概率就是边界写错了。给你几个我自己常用的调试手段。

第一，小范围验证。把n设成100，然后从小到大打印所有标记情况，肉眼核对质数序列：2、3、5、7、11……如果某个数被错误标记，一眼就能看出来。

第二，写一个暴力对照函数。随机挑几组数据，用简单判断法验证某个数到底是不是质数，再和筛法结果比对。比如可以写个isPrimeByBruteForce(x)，然后从1到1000遍历一遍，任何不一致都能快速定位。

第三，善用断言。在代码里加一行assert，筛选完之后检查关键结论，比如2一定是质数，4一定不是质数，等等。这能帮你把逻辑错误挡在输出之前。

#include <cassert> assert(isPrime[2] == true); assert(isPrime[4] == false);

这种检查会在程序异常时立刻报错，比你自己一行行看输出高效太多。考场里可能没时间写这些，但平时练习一定要养成这个习惯。

5.3 筛选后的策略与个人习惯

我个人在五级这个阶段更推荐先把埃氏筛吃透，因为它代码量小，逻辑清晰，考场犯错的概率低。但线性筛也不要只停留在“会默写”的程度，要能用自己的话解释清楚那个break到底在干什么。你把原理彻底理解了，就算考场紧张写错了一两行，复查时也能很快发现。

至于数组命名和变量命名，我习惯用isPrime表示质数标记表，用composite表示合数标记表，用primes存质数列表。命名清楚能直接降低你自己的思维负担。哪怕考试时间紧，也别写一堆a、b、c这种变量，一旦出错，你连代码都读不下去。

最后一个建议：筛法函数里尽可能用全局或静态数组。局部大数组开在栈上，n一大就可能栈溢出；全局数组放在静态存储区，空间宽裕得多。我这个习惯救过很多人，也希望能帮你少踩一次坑。