如果你在洛谷上刷到 P5736【深基7.例2】质数筛大概率是刚学完数组和循环正被“筛”这个字整得有点懵。题目长得很简单给你 n 个整数把里面的质数输出。可它偏偏叫“质数筛”而不是“质数判断”这就是出题人埋在标题里的提示——想让你用筛法批量解决而不是对每个数傻乎乎地做试除。很多同学把洛谷题库当成闯关小游戏一题一题往下刷这道题就是数组章节里非常经典的一关。这篇文章我会从题目考点入手把埃氏筛的原理、完整 C 代码、Java 移植版、洛谷上容易踩的坑全部讲一遍。最后还会聊聊我实际刷这题时总结出的几个习惯包括很多人遇见过但不知道怎么办的“提交失败无法解析路由对象”这种与环境无关的报错。无论你是刚入门算法半个月的新手还是被老师布置了这题的课代表照着这篇文章走一遍基本能一次过。1. 题目到底在考什么不是让你“判断”而是让你“筛”1.1 质数判断和质数筛有什么区别先说清楚一个概念性问题判断单个质数和批量筛质数是两回事。试除法的思路很直白对每个数 x从 2 枚举到 sqrt(x)看看是否存在能整除它的数。这种方法在处理“单独判断一个大数是不是质数”时没问题但本题输入的是 n 个整数n 最大到 100如果每个数都要从 2 试到 sqrt(x)虽然数据量小的时候也能过但那不是出题人想看到的写法。筛法就不一样了。筛法更像是“用一个筛子把所有候选数过一遍”开一个足够大的布尔数组先把所有位置标记为“是质数”然后从 2 开始把每个质数的倍数全部标记成“不是质数”。等这一轮标记全部结束数组里还保持“是质数”状态的位置就是我们要找的质数。这个过程中所有数字只被当作“位置”处理一次所以它是批量操作天然适合题目这种“多输入、多输出”的场景。两者的时间复杂度差别很明显。试除法最坏情况下要做 n 次独立的 sqrt 级别运算复杂度大概是 O(n * sqrt(V))其中 V 是输入数字的上限。埃氏筛只需要做一次预处理复杂度是 O(V * log log V)预处理完之后再判断任何一个数是不是质数只需要查一次数组时间复杂度是 O(1)。当输入数量变多、数值范围变大时筛法的优势会越来越大。这也是为什么题目名称里特意带了一个“筛”字它就是给你划重点。1.2 先想清楚输入输出再动手写代码很多新手一看到“质数”两个字就急着开写结果要么数组开到 n要么忘记处理 1要么输出格式不对。其实这类题目在动手前应该先把输入输出结构理一遍。第一行是一个正整数 n表示接下来会有多少个数字。第二行是 n 个正整数我们需要按原来的顺序输出其中所有的质数数与数之间用空格隔开。如果这一组里一个质数都没有那就只输出一个换行不要输出多余内容。这里有一个非常关键的细节筛子数组的大小不应该由 n 决定而应该由这一组输入里的最大值决定。比如 n 等于 3输入是 100000、99991、2那么筛子至少要能覆盖到 100000。如果因为 n 只有 3就把数组开到 105那查表的时候直接数组越界轻则答案错误重则段错误崩溃。正确做法是读入所有数字的同时记录一个 maxVal然后以 maxVal 作为筛子的上界。还有一个容易被忽略的点数字 1 不是质数。程序里如果只从 2 开始筛而不把 1 单独标记成“不是质数”那么当输入里出现 1 的时候它会被错误地当作质数输出。处理办法很简单初始化时把 isPrime[0]、isPrime[1] 都置为 false 就行。2. 埃氏筛的核心原理一句话加一个例子2.1 核心逻辑质数的倍数一定是合数埃氏筛只需要记住一句话一个质数的倍数一定是合数。这句话是整个算法的根基。假设我们要筛出所有不超过 V 的质数就先开一个长度为 V1 的布尔数组初始全部为 true。然后从 2 开始往后扫如果当前位置的值还是 true说明这个数没有被更小的质数标记为合数那它就是一个质数此时把它所有的倍数全部标记为 false。如果当前位置已经是 false说明它是某个质数的倍数直接跳过。这样一轮扫完数组中所有值为 true 的位置除了 0 和 1 这两个我们提前处理掉的特殊值剩下的就是完整质数表。这个逻辑非常好理解。4 是 2 的倍数所以 4 是合数6 是 2 的倍数也是 3 的倍数所以 6 是合数9 是 3 的倍数所以 9 是合数。反过来说一个数如果没有被任何小于它的质数标记为倍数那它就不可能存在大于 1 且小于它本身的因子它就只能是一个质数。2.2 完整手算演示筛出 30 以内的质数我一直觉得理解一个算法最快的方式就是拿小数据手算一遍。假设我们要筛出不超过 30 的质数过程是这样的。初始时我们认为 2 到 30 全部都是质数。先看 22 当前是 true所以 2 是质数随后把 4、6、8、10、12、14、16、18、20、22、24、26、28、30 全部标记为 false。接着看 33 没有被 2 标记所以 3 是质数把 9、12、15、18、21、24、27、30 标记为 false。4 已经被标记过跳过。接下来是 55 还是 true所以 5 是质数把 25、30 标记为 false。再往下 6、8、9、10 等都已经变成 false 了。扫到 7 时7 仍然是 true于是 7 也是质数。此时我们原本要做的操作是标记 14、21、28但这些数字早就被 2 和 3 标记过了所以实际上从 7 开始标记动作几乎没有新增内容。最后保留为 true 的数字是2、3、5、7、11、13、17、19、23、29。检查一遍30 以内的质数确实就是这十个。2.3 两个关键优化搞懂原理就能记住埃氏筛有两个非常经典的优化理解了之后基本不会忘。第一个优化是外层循环只需要走到 sqrt(maxVal)。原因是这样的假设某个合数 m 存在于我们要筛的范围内那么 m 一定可以拆成两个因子 a 和 b 的乘积并且其中较小的那个因子不会超过 sqrt(m)不会超过 sqrt(maxVal)。这个较小因子的质因子必然在枚举到 sqrt(maxVal) 之前就被处理过因此 m 一定会在那之前被标记为合数。继续让外层循环往后走并不会产生任何新的标记只会浪费运行时间。第二个优化是内层循环从 ii 开始而不是从 2i 开始。很多人刚写埃氏筛时会写for (int j 2 * i; j maxVal; j i)这样写逻辑上没错但做了大量重复标记。比如 i 5 时25 等于 1010 早在 i 2 的时候就被标记过了35 等于 1515 早在 i 3 的时候就被标记过了45 等于 2020 也被 i 2 标记过。真正第一次有可能被 5 新标记出来的是 55 等于 25。所以从 i*i 开始不仅能保证不遗漏还能减少大量重复操作。3. C 完整实现与逐段解读3.1 可直接提交的 C 代码下面这版代码是我比较推荐的写法。它先读入全部数据并记录最大值然后用动态数组作为筛子既稳定又不会出现数组开小的问题。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); 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]); } // 用 vectorchar 模拟布尔数组避免 vectorbool 的位压缩问题 vectorchar isPrime(maxVal 1, true); if (maxVal 0) isPrime[0] false; if (maxVal 1) isPrime[1] false; // 埃氏筛核心外层只需要到 sqrt(maxVal) for (int i 2; (long long)i * i maxVal; i) { if (isPrime[i]) { // 从 i*i 开始标记避免重复标记更小的倍数 for (int j i * i; j maxVal; j i) { isPrime[j] false; } } } // 按原顺序输出质数使用 first 变量控制空格格式 bool first true; for (int x : a) { if (isPrime[x]) { if (!first) cout ; cout x; first false; } } cout \n; return 0; }我解释几个容易被忽略的细节。第一vectorchar在这里不是真的存字符而是用它代替布尔数组。因为标准库里的vectorbool做了位压缩读写时会带来额外开销在某些评测环境下会慢一些而且它的行为比较特殊新手容易踩坑。用vectorchar或vectorint会直白很多。本题数据量很小内存完全不是问题。第二为什么要在i * i maxVal这里把i强转成long long因为如果maxVal足够大比如到 10^7i * i将可能达到 10^14超过int的表示范围导致溢出变成负数循环条件直接乱套。虽然本题数据一般到不了这个量级但写代码时保留这个好习惯以后遇到更大的数据范围就能少一次崩溃。第三内层循环用j i每次跳一个i的步长这是筛法效率的关键。如果误写成了j那复杂度会瞬间退化到 O(V^2)数据稍大一点就会超时。3.2 时间复杂度与空间复杂度分析埃氏筛的时间复杂度是 O(maxVal * log(log(maxVal)))。这个复杂度看起来有点奇怪其实是数论里的一个常见结论。简单理解就是每个质数 p 要把 maxVal/p 个倍数标记掉把所有质数的标记工作量加在一起总量大约是 maxVal * log(log(maxVal)) 这么一个级别。实际运行效率非常高即使 maxVal 是 10^7也只需要几十毫秒量级的计算量。空间复杂度是 O(maxVal)因为我们开了一个长度为 maxVal1 的布尔数组。在本题常见的约束下比如 maxVal 是 10^5 或 10^7这个数组占用空间非常小如果是vectorchar10^7 个元素也就 10MB 左右洛谷完全能扛住。3.3 不同数据范围下的选型建议如果输入数字的最大值只有 10^5埃氏筛和试除法都能轻松通过。但如果 maxVal 继续增大到 10^8 甚至更大埃氏筛的时间还能勉强撑得住内存就要精打细算了。这时候可以考虑bitset压缩存储或者在筛选时只处理奇数位置把空间减半。再大一些比如要求预处理 10^9 以内的质数那就不是一道基础题该考虑的事了通常会用分段筛。所以面对 P5736 这题直接用埃氏筛是最合适的选择。它代码短、原理清晰、性能足够同时也为你将来处理更复杂的质数问题打下了基础。4. 初学最容易踩的 5 个坑附排查思路4.1 数组开太小导致越界或段错误这个坑非常经典。很多同学刚学数组习惯用bool isPrime[105]之类的定长数组然后发现输入里有一个很大的数直接访问isPrime[x]时越界。程序可能直接崩溃也可能给出一个莫名其妙的答案。解决办法就是我在前面反复强调的那句先读入所有数据记录最大值再创建数组。用vector动态分配让数组大小精确等于maxVal 1永远不用担心上限问题。4.2 把 1 当成质数输出1 不是质数这是数学定义但程序里如果你不主动处理它会被默认当成质数。代码如下if (maxVal 0) isPrime[0] false; if (maxVal 1) isPrime[1] false;这两行放在埃氏筛之前保证 0 和 1 这两个特殊值从一开始就被判为“合数”。如果漏掉了样例中一旦出现 1输出结果就会多一个 1直接 WA。4.3 忘记初始化或者初始化方式不对本题中我们需要先把数组全部设为 true因为筛法默认所有数都是质数然后再逐步排除合数。如果你用的是vectorchar isPrime(maxVal 1, true)初始化就完成了。但如果你手动开一个普通的 bool 数组一定要用memset或者循环把每个位置都赋值不能只初始化一部分。还有一种情况是你写的是vectorchar isPrime(maxVal 1, false)然后把“true 表示合数”作为相反的逻辑。这种思路不是不行但容易让自己绕晕。我建议按最常规的语义来写isPrime[x] true表示 x 是质数。4.4 输出格式不对多余空格和缺少换行洛谷对输出的判断比较严格。虽然大多数题目会忽略行尾多余空格但最好不要赌。常见错误是在每个数前面都加一个空格导致第一个数前面多了一个空格。或者最后少输出换行。我习惯用bool first来标记当前是否已经输出过第一个数。第一个数前不输出空格后续每个数前都输出一个空格。最后统一输出一个换行。这样格式一定正确。4.5 洛谷提交报错“无法解析路由对象”别急这多半不是代码问题最近有不少同学在洛谷提交时看到这样的提示“the route object cannot be resolved”或者“提交失败无法解析路由对象”。第一次遇到这个问题的人很容易慌以为是代码跑挂了其实这个报错大多数情况下是洛谷网页前端或者网络环境的问题跟你的代码一点关系都没有。遇到这个报错你可以按顺序尝试以下操作刷新当前页面再点一次提交。退出账号重新登录。清一下浏览器缓存或者把网址从 http 改成 https。换一个浏览器或者开启浏览器无痕模式。等几分钟后再试。洛谷偶尔会有服务器波动过一会儿自己就好了。如果一直不行先用洛谷的“在线 IDE”跑一遍代码确认代码本身能运行、输出样例正确再回去重新提交。特别提醒如果你看到的是“提交失败”而不是“答案错误”或“编译错误”那就说明评测系统根本没有收到你的代码这个时候反复修改代码没有意义应该先解决网络和页面的问题。4.6 用边界数据自查代码提交之前建议先用几组极端数据自测一下。你可以把这些数据依次粘贴到洛谷的在线 IDE 里运行检查输出是否符合预期。输入51 2 3 4 5期望输出2 3 5输入11期望输出一个空行输入34 6 8期望输出一个空行输入62 3 5 7 11 13期望输出2 3 5 7 11 13这几组用例分别覆盖了含 1、无质数、全为质数、全为合数的情况。只要它们都能通过你这道题的正确率就非常稳了。5. Java 版怎么做以及更进一步线性筛5.1 Java 实现埃氏筛用 Java 刷洛谷的同学也很多所以我补一个 Java 版本。核心逻辑和 C 版本完全一样只是换了一套语法外壳。import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] a new int[n]; int maxVal 0; for (int i 0; i n; i) { a[i] sc.nextInt(); maxVal Math.max(maxVal, a[i]); } boolean[] isPrime new boolean[maxVal 1]; Arrays.fill(isPrime, true); if (maxVal 0) isPrime[0] false; if (maxVal 1) isPrime[1] false; for (int i 2; (long) i * i maxVal; i) { if (isPrime[i]) { for (int j i * i; j maxVal; j i) { isPrime[j] false; } } } StringBuilder sb new StringBuilder(); for (int x : a) { if (isPrime[x]) { if (sb.length() 0) sb.append( ); sb.append(x); } } System.out.println(sb); sc.close(); } }这里最需要注意的是boolean[]数组创建后默认全是 false必须用Arrays.fill(isPrime, true)把所有位置都改成 true否则筛法会得出完全相反的结果。5.2 从埃氏筛到欧拉筛线性筛埃氏筛虽然已经很快但它有一个小问题同一个合数可能被多个质数重复标记。比如 30它会被 2 标记一次被 3 标记一次被 5 标记一次总共被标记了 3 次。这种重复标记不影响正确性但会多消耗一点时间。欧拉筛也叫线性筛它的目标是保证每个合数只被它的最小质因子标记一次从而把时间复杂度严格控制在 O(maxVal)。vectorint primes; vectorchar isComp(maxVal 1, false); // 标记合数 for (int i 2; i maxVal; i) { if (!isComp[i]) { primes.push_back(i); } for (int p : primes) { if ((long long)i * p maxVal) break; isComp[i * p] true; if (i % p 0) break; // 关键保证 p 是 i 的最小质因子 } }在这段代码里最关键的一行是if (i % p 0) break;。它保证了每个合数只会被它的最小质因子筛掉。比如当 i 4 时质数表里有 2 和 3。先筛掉 8此时 4 能被 2 整除所以立即跳出循环不再筛 12。因为 12 的最小质因子是 2应该留给后面更大的 i 去筛而不是在这里用 3 去标记。很多模板题比如“线性筛素数”用的就是这套思路。它比埃氏筛稍难理解一点但代码短性能更稳定。5.3 面对 P5736 这题选哪种筛更合适我的建议是先把埃氏筛写熟再了解线性筛。P5736 的数据范围非常友好埃氏筛完全够用代码也更直观。如果你一开始就直接上线性筛虽然也能过但可能因为原理没吃透反而在后来的变种题里吃亏。从学习曲线来看埃氏筛负责建立“批量标记”的直觉线性筛负责让你明白“最小质因子”这个概念。这两者不是谁替代谁的关系而是递进关系。先把埃氏筛搞懂再把线性筛学会质数相关的题基本就稳了。6. 刷这题时我养成的几个习惯6.1 把筛法代码沉淀成模板第一次 AC 之后我建议把自己的代码整理成一个可复用的模板保存到本地或博客里。模板里至少要有输入、取最大值、初始化、筛选、输出这五个部分。以后再做其他需要筛质数的题直接把这个模板抄过来改改就行能省下大量重复时间。我最常用的模板其实就是第 3 节那段代码。它的通用性很强只需要修改数组大小和筛选上限就能处理其他题目里的质数预处理问题。你也可以把埃氏筛和线性筛各存一份放到同一个文件里方便对比记忆。6.2 刷完这题后下一步可以练什么如果这道题你已经完全懂了可以去洛谷搜“线性筛素数”的模板题那里会要求你输出 1 到 n 范围内的所有质数正好能练习线性筛。也可以找几道需要用到质数判断或分解质因数的题目做一做加强一下应用能力。等基础题刷得差不多了再往复杂的方向扩展比如最长公共子序列、DAG 上的最长路、图论相关的动态规划题那些都会用到类似的“先预处理、再计算”的思维方式。不过那是后话先把 P5736 稳稳拿下再说。最后说一句我的真实体会。第一次提交这题时我因为忘记把 1 标记为合数样例输出里多了一个 1整整卡了十分钟。后来我把筛法的固定流程背熟每次写完都主动检查边界值就再也没有在这种基础题上翻过车。刷题这事儿很多时候不是算法有多难而是细节有没有做到位。希望你读完这篇文章也能少踩几个坑一次 AC。