做算法题这些年如果让我给新手推荐一道“用小题目理解大思想”的入门题洛谷 P5736【深基7.例2】质数筛 一定是首选。它的题面相当朴素给你若干个整数让你把里面的质数全部输出。但你真按最直觉的方式一个个去判断数据稍微大一点就会吃瘪而真正优雅的解法是“筛”——先把一定范围内的质数表全部算出来之后每一个数字都变成查表操作。这篇文章就是围绕这个思路把它的原理、两种主流实现、完整AC代码和我踩过的坑讲透。这道题被洛谷放在“深基7”的第二章位置很微妙。它表面上看是数组练习实际上是你第一次系统性接触“预处理”思想的地方。学会这题你后面遇到前缀和、差分、并查集、甚至DP状态预处理都会有一种“啊原来还是这个套路”的顿悟感。所以别把它当普通水题刷完就扔值得多花点时间琢磨。适合谁来读刚学C或Java、准备蓝桥杯或NOIP普及组、以及所有被“超时”折磨过的同学。我把完整的思考过程、两套筛法模板、提交时容易踩的坑都写出来了你可以直接拿去用。1. 题目到底在考什么从“判断质数”到“筛质数”1.1 题面拆解与隐藏门槛先花十秒钟回忆一下题面第一行给一个 n第二行给 n 个整数要求把其中所有质数输出空格分隔。数据范围一般是 n 不超过 100每个数不超过 10^7。限定“ai ≤ 10^7”这个条件就是最大的提示。很多第一次做这道题的人第一反应都是写一个isPrime(x)函数从 2 一直枚举到 sqrt(x)逐个判断是质数就输出。这个做法从逻辑上没有任何问题甚至在这个数据范围下能通过。但这道题叫“质数筛”题目的意图非常明显它要你换一种思路不是“判断一个数是不是质数”而是“提前把所有质数都筛出来然后查表”。为什么题目要这么设计因为“判断质数”是单次操作而“筛质数”是批量操作。如果数据范围扩大到 n 10^6每个数接近 10^7朴素判断的时间就会变得不可接受。筛法一次性把 1 到 max 范围内的质数全部算出来查询时 O(1) 输出这才是竞赛里真正需要的效率。1.2 为什么朴素判断不够用我们来估算一下朴素判断的时间。假设一个数 x判断它是否为质数需要做 sqrt(x) 次取模运算。当 x 10^7 时最多大约 3162 次运算。n 100 个数总共大约 30 万次运算看上去不多吧但是——如果题目把范围改成 n 10^5每个数还是 10^7 级别那就是 3 亿多次运算即使 C 也跑得很吃力。而筛法呢筛到 10^7 只需要大约 0.1 秒级别之后每个数查一次表输出完事。这就是“预处理 查询”的威力。它把大量重复计算变成一次性的预计算再用空间换时间。这个思维转变比这道题本身重要得多。很多新手在入门阶段会有一个误区能过样例就行、能过题就行。但竞赛题真正考你的是你能不能想出一个在极端数据下依然高效的方案。质数筛就是这样的第一个台阶。1.3 用空间换时间的核心思路筛法的核心数据结构就是一个布尔数组通常叫isPrime或isComposite。初始化时假设所有数都是质数然后从 2 开始一旦确认某个数是质数就把它的所有倍数全部标记为合数。走完整个过程剩下的没有被标记过的数就都是质数。这里有一个细节很多人刚开始会忽略标记倍数时的起点。比如筛 2 的倍数时可以从 4 开始也可以从 6 开始但从 4 开始就够了吗对 2 来说2 * 2 4所以从 4 开始没问题。但对 3 来说3 * 2 6而 6 已经被 2 标记过了重复标记毫无意义。所以埃氏筛的经典写法是j i * i开始标记因为比i * i小的i的倍数一定已经被比i小的质因子筛过了。比如 5 的倍数里10、15、20 分别被 2、3、2 筛过不需要再管直接从 25 开始才能保证每个合数第一次被标记时就落在它的最小质因子上。这个“起点优化”看起来不起眼但在 10^7 的数据量下能省掉大量的重复标记运行时间差好几倍。我当年没注意这个细节照着j 2 * i写提交之后慢了 200 多毫秒当时还以为是评测机波动后来才反应过来是重复标记太多。2. 两种经典筛法埃氏筛和欧拉筛2.1 埃氏筛最好懂的筛法埃拉托斯特尼筛法简称埃氏筛是筛法里最经典、最直观的一种。思路就是从小到大遍历每一个数如果这个数没有被标记为合数那它就是质数然后把这个质数的所有倍数标记为合数。vectorbool isPrime(maxN 1, true); isPrime[0] isPrime[1] false; for (int i 2; i * i maxN; i) { if (isPrime[i]) { for (int j i * i; j maxN; j i) { isPrime[j] false; } } }这段代码里内层循环的起点是i * i原因上面已经说过。外层循环只需要走到sqrt(maxN)就够了因为当 i 超过 sqrt(maxN) 时i * i已经越界不可能再标记任何新合数了。这也是一种剪枝。埃氏筛的时间复杂度是 O(n log log n)空间复杂度 O(n)。对于 10^7 级别的数据绰绰有余。它最大的优点是容易理解、不容易写错特别适合做题时手速快、求稳的情况。缺点是同一个合数可能被多个质因子重复标记比如 12 既会被 2 标记又会被 3 标记存在冗余。实际做题时埃氏筛是我个人最推荐的模板。它代码短思路清晰改写灵活不管面对什么题目先能跑出正确答案再说。至于那一点冗余在竞赛评测里通常无伤大雅。2.2 欧拉筛每个合数只标记一次欧拉筛也叫线性筛是埃氏筛的进阶版。它的核心目标就是消除重复标记让每一个合数只被它的最小质因子标记一次从而把时间复杂度严格降到 O(n)。欧拉筛的代码比埃氏筛略绕一点但它解决的问题非常具体vectorint primes; vectorbool isComposite(maxN 1, false); for (int i 2; i maxN; i) { if (!isComposite[i]) { primes.push_back(i); } for (int j 0; j primes.size() i * primes[j] maxN; j) { isComposite[i * primes[j]] true; if (i % primes[j] 0) break; // 核心 } }理解这段代码的关键在if (i % primes[j] 0) break;。它保证了当primes[j]能整除i时就停下来不再用更大的质数去标记。为什么因为一旦primes[j]是i的因子那么i * primes[j1]这个合数将来一定会被一个更小的质因子标记现在标记它纯粹是浪费。举个例子i 4 时primes 表里已经有 2、3。先标记4 * 2 8然后4 % 2 0break不再标记4 * 3 12。因为 12 的最小质因子是 2将来当 i 6 时6 * 2 12会被正确标记一次。这个 break 保证了线性筛的“线性”。欧拉筛的缺点是代码理解成本高边界条件容易写错。如果只是解 P5736 这一道题杀鸡用牛刀。但如果你想为后面更大的数据范围打基础比如 10^8 级别的质数表欧拉筛就派上用场了。2.3 两种筛法怎么选两个筛法用哪个我给一个很直白的建议入门阶段能写对埃氏筛就先用埃氏筛。它应对绝大多数题目都够了。等你把埃氏筛写熟了、理解了为什么从i * i开始再去啃欧拉筛。不要一上来就追“最优解”先把“能用的解”做对再谈优化。对比维度埃氏筛欧拉筛线性筛时间复杂度O(n log log n)O(n)代码难度低中重复标记有无适合场景普通入门题、快速求解大数据量、进阶题型出错概率低中如果是比赛我的习惯是确认数据范围后10^7 以内直接用埃氏筛10^7 以上或者题目明确卡常再换成欧拉筛。毕竟在绝大多数题目里这两种筛法的实际差距也就是几十毫秒远不如一次 WA 来得痛。3. 本题完整实现与AC代码3.1 C完整代码展示这道题里n 不大但数字最大可能到 10^7所以筛法数组要开到最大数字的规模。一个很常见的错误是拍脑袋把数组开到1000005结果输入里有个 9999999直接越界。正确做法是先读入所有数找到最大值再开数组。下面是我提交过的完整代码埃氏筛版本#include bits/stdc.h using namespace std; const int MAXA 10000005; bool isPrime[MAXA]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; vectorint a(n); int maxVal 0; for (int i 0; i n; i) { cin a[i]; maxVal max(maxVal, a[i]); } // 初始化 memset(isPrime, true, sizeof(isPrime)); isPrime[0] isPrime[1] false; // 埃氏筛 for (int i 2; i * i maxVal; i) { if (isPrime[i]) { for (int j i * i; j maxVal; j i) { isPrime[j] false; } } } // 输出结果 bool first true; for (int i 0; i n; i) { if (a[i] 2 isPrime[a[i]]) { if (!first) cout ; cout a[i]; first false; } } return 0; }这段代码有几个细节需要注意memset(isPrime, true, sizeof(isPrime))是可以的因为 bool 在 C 中按整型处理全字节填充 1即 trueisPrime[0] isPrime[1] false必须手动处理因为 0 和 1 不是质数。输出时按题目要求用空格分隔我加了一个first标志位避免行末多输出空格导致格式错误。3.2 关键代码逐段解释先看memset这一行。很多初学者会遇到一个问题数组开到 10^7 量级时普通赋值for (int i 0; i MAXA; i) isPrime[i] true;可能要跑几十毫秒而memset是内存级别的操作速度更快也更简洁。不过memset只适合“全填 0 或全填 1”的情况不能填任意值。再看筛法循环。外层for (int i 2; i * i maxVal; i)的终止条件是i * i maxVal等价于i sqrt(maxVal)。为什么只到 sqrt因为如果 i 超过了 sqrt(maxVal)那么i * i已经超过 maxVal内层循环一次都不会执行继续遍历就是浪费时间。这里用i * i而不是先算sqrt(maxVal)是为了避免浮点数精度问题虽然在这个数据范围内用 sqrt 也不会出错但养成用乘法比较的习惯会更稳。内层for (int j i * i; j maxVal; j i)是筛法的主体。注意j是int类型当maxVal接近 10^7j i最多到 10^7不会溢出 int。但如果以后处理更大的范围比如 10^9i * i就可能超过 int 上限一定要把循环变量改成long long这是非常经典的溢出坑。输出部分我特意判断了a[i] 2防止数组下标访问isPrime[0]和isPrime[1]。虽然我已经给这两个位置赋了 false但这个判断能让代码逻辑更清晰只有大于等于 2 的数才可能成为质数。同时用first标志控制空格避免输出末尾多一个空格这种格式在洛谷上严格卡 PEPresentation Error时很重要。3.3 Java版的差异与注意点热词里有“java洛谷”可见不少同学在 Java 环境下刷题。Java 写这道题有几个和 C 不太一样的地方先说结论纯算法逻辑相同但数组初始化和输入输出的写法需要做出调整。Java 里创建布尔数组boolean[] isPrime new boolean[maxVal 1];默认值是 false所以需要先Arrays.fill(isPrime, true);。Arrays.fill在 10^7 量级下可能稍慢但也还好。筛法循环体基本一样只是数组下标访问时 Java 会做边界检查速度比 C 慢如果数据再大一点可能要考虑用BitSet优化内存和速度。输入输出方面强烈建议用BufferedReaderStringBuilder代替Scanner和逐行System.out.print。Scanner在 10^5 级别输入时就可能成为瓶颈而BufferedReader快很多。输出时先拼接到StringBuilder最后一次性输出也能减少 I/O 开销。BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); // 读入所有数字寻找最大值然后筛法最后拼接输出洛谷的 Java 环境一般会比 C 慢一倍左右所以如果题目卡时间Java 代码要注意优化。不过 P5736 数据范围友好Java 使用上述优化也是轻松通过。4. 踩坑与疑难排查那些年我交过的WA4.1 五个最容易犯的逻辑错误先说逻辑类错误每一个我都亲眼见过有些还亲手犯过。第一忘记处理 1。1 不是质数也不是合数。如果你开筛法数组时没有显式把isPrime[0]和isPrime[1]设成 false那么输入里出现 1 时你的程序会把它当质数输出。这个 bug 非常隐蔽因为样例里往往没有 1。第二筛法数组开小了。这是最冤的错。很多人看到 n ≤ 100就以为数组开到 100 就行忘了数组下标对应的是数本身而不是数的个数。数组必须开到“最大可能输入值”那么大而不是“输入个数”那么大。正确做法是读入完之后动态找最大值再按最大值创建数组。第三内层循环起点写成2 * i。前面说过从i * i开始能避免重复标记。如果你的代码从2 * i开始在数据范围内也能出正确结果只是慢一点。但在某些变态数据下重复标记会多到超时所以养成从i * i开始的好习惯。第四欧拉筛漏写 break。如果是从埃氏筛转向欧拉筛很容易把if (i % primes[j] 0) break;这行漏掉。漏掉之后功能上依然能筛出质数但筛法从“线性”变成了“类似埃氏筛”不但变慢某些边界情况下还会重复标记数组越界。欧拉筛的 break 是灵魂不能丢。第五错误使用sqrt判断。有些人判断质数时喜欢写for (int i 2; i sqrt(x); i)但如果你漏了#include cmath或者把sqrt放在循环条件里反复计算都会带来性能问题。更稳妥的做法是写for (int i 2; i * i x; i)。4.2 洛谷提交环境的“伪故障”还有一个和代码逻辑无关但会把你气得半死的问题。热词里出现了“the route object cannot be resolved”“提交失败无法解析路由对象”我遇到过一次。这种情况通常不是你的代码有错而是洛谷的评测机或本地网络出现了瞬时故障也可能是浏览器缓存的问题。我的处理办法是先复制好代码刷新页面重新点提交如果不行换一个浏览器或者无痕模式再试再不行清一下 DNS 缓存或换个网络环境。一般重试一次就恢复了。千万别因为提交失败就反复改代码最后把自己改出一堆新 bug。还有个更常见的问题洛谷提交时会有一段时间的“评测队列拥堵”提交后老是在“等待评测”。这时候不要重复提交避免评测机压力更大。我看到有人连续点了十几次提交最后系统判定重复提交反而拖慢了所有人的评测速度。等一两分钟基本都能出结果。4.3 常见问题速查表问题表现可能原因解决方案1 被错误输出没给 isPrime[0]、isPrime[1] 赋 false筛法前手动处理 0、1数组越界数组大小按 n 开而非按最大数字开读入后取 maxVal 再建数组超时内层循环从 2*i 开始重复标记多改成从 i*i 开始欧拉筛多个合数重复标记漏写 break补上 i % primes[j] 0 判断提交失败显示路由错误网络或评测机瞬时故障刷新后重试不要反复改代码输出末尾多空格循环里直接 cout x 用 first 标志控制分隔符5. 从这题延伸出去筛法思想才是主角5.1 筛法思想还能用在哪做完这一题别急着往下刷。你先停下来想一想筛法到底解决了一个什么问题它解决的是“在某个范围内一次性求出大量数据的特征”的问题。这个思想在竞赛里到处都能见到。比如前缀和。给你一个数组问你很多次某个区间的和如果你每次都遍历一遍总时间复杂度是 O(nq)q 大一点就崩。但如果先预处理出前缀和数组每个区间和就变成一次 O(1) 减法。这和筛法“先预处理、再快速查询”的思路如出一辙。再比如判断一个数是不是素数这件事本身。很多题目要求多次判断多个数是否为质数还要配合质因数分解。这时候先用筛法把质数表打出来再用质数表去试除效率远超对每个数单独判断。像“求出区间 [L, R] 内的质数个数”这类题很多都需要先做一次全局质数筛再配合前缀和快速回答。如果你往后学会数论会发现筛法还能筛莫比乌斯函数、筛欧拉函数、筛约数和函数。所谓“积性函数都可以用线性筛来预处理”欧拉筛的框架可以推广到这些场景。也就是说你今天在 P5736 里学到的不是一个孤立的知识点而是一整套数论预处理工具的基石。5.2 后续可以刷什么题加深理解洛谷的题单很贴心在“深基”系列之后会有大量用到筛法的题目。我个人的建议是刷题顺序可以这样安排先把 P5736 的埃氏筛和欧拉筛都写一遍感受两者差异然后去找一些需要你“判断质数 质因数分解”的题练手如果你对数学兴趣浓厚再去接触反演相关的题目。新生不要急着追求刷题数量。我在带人的时候发现真正拉开差距的往往是基础题的深度。同样是 P5736有人写完答案就翻篇有人会把埃氏筛改成欧拉筛再对比运行时间再把筛法封装成函数再思考如果输入数据是 10^8 怎么办。后者经过这一道题基本就把“筛法”这个知识点吃透了。前者遇到同类型变体题大概率还会卡。我个人在实际操作中的体会是一道题能不能给你带来指数级的成长不取决于它本身的价值而取决于你愿意在它身上挖多深。P5736 的题面很“素”但它背后站着的是整个算法竞赛中最重要的预处理思想。把这一题真正消化掉比囫囵吞枣地刷十道简单题有用得多。最后再分享一个小技巧写完代码别急着提交先自己构造几组边界数据测一测比如 n 1 且输入 1、输入全是合数、输入里包含最大值 10^7、输入里全是 2。这几组数据过了你的代码基本就稳了。这个习惯是我踩了无数次 WA 之后才养成的现在免费送给你。
