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×210已经被2划掉5×315已经被3划掉5×420也已经被2划掉了。真正需要通过5来划掉的至少是5×525。所以从ii开始既不会漏也能减少大量重复的赋值操作。第二个优化是外层循环只到√n就停。你想如果n是合数那它一定有一个因子不超过√n。既然所有涉及小因子的合数都已经在小因子那轮被划掉了那超过√n的大因子对应的合数自然早就被标记过了不需要再继续跑。2.2 一段可以直接上考场的埃氏筛直接给一段我比较常用的写法#include bits/stdc.h using namespace std; const int MAXN 1000000; vectorbool 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^9i*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也还在可接受范围内。更极端的情况才需要考虑线性筛或进一步优化。所以如果你参加五级考试说明考试范围通常不会给你一个n10^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]再标记一次等于白做了重复功破坏了“只筛一次”的原则。举个例子。处理到i4时质数表里有2、3。先用2做标记4×28标记没问题再看4%20于是break不处理4×312。等到i6时6%2也等于0标记完6×212后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或vectorchar不要图省事直接用vectorbool以外的奇怪类型。primes数组的容量按照n来开就够实际质数个数远小于n开大一点只是多占点内存不会有问题。我习惯开成n5既保险又不用记精确公式。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]里对应的合数。因为区间长度不大用一个偏移数组就够了。核心代码可以这样写vectorbool 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 两种筛法在实际运行中的表现对比我给一个参考性的对比表方便你心里有数方案时间复杂度空间占用五级场景下的性价比逐个暴力判断O(n√n)极小只适用于n≤1000埃氏筛O(n log log n)O(n)代码短、稳默认首选线性筛O(n)O(n)理解门槛稍高扩展性强很多人误以为线性筛一定比埃氏筛快很多其实不一定。线性筛为了追求“每个合数只标记一次”多做了很多取模和压栈式判断常数并不小。在小数据范围下两者实测时间往往差别不大甚至埃氏筛因为代码更简单编译优化后反而可能更快一点。所以考试取舍很简单只求质数写埃氏筛要顺便算数论函数再上线性筛。别为了炫技去用复杂方案考场里“写得出来”比“理论上更快”重要得多。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;这一字之差会让循环继续跑破坏线性性质虽然小数据下可能看不出问题但大数时会有重复标记。四是vectorbool的使用误区。vectorbool是位压缩版本节省空间但它的操作效率和普通bool数组不太一样。想偷懒时可以直接用vectorchar至少不会因为某些引用问题导致意外调试困难。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一大就可能栈溢出全局数组放在静态存储区空间宽裕得多。我这个习惯救过很多人也希望能帮你少踩一次坑。