1. 一道入门题为什么会跟“筛法”绑定在一起1.1 题面在考什么函数封装才是这题的“正餐”先说结论P5736是洛谷“深入浅出”系列第七章的例题这一章的主题是函数与结构体。所以这题表面上在考“怎么判断质数”实际上章节的教学目标是把判断逻辑写成一个干净的函数用传参的方式去处理每一个输入值。很多人第一次做这题时直接在main函数里套两层循环边读边判断边输出代码写得又长又乱虽然能过但完全没有领会这一章的用意。题面本身不复杂输入一个n再给n个整数把其中所有的质数按顺序输出空格分隔。数据范围有两个第一行n不超过100第二行每个数字不超过10^9。这个范围设计得很讲究——10^9这个量级恰好卡在“暴力能不能过”的临界点上也是很多初学者第一次感受到“算法选择”的地方。1.2 数据范围是选算法的关键暴力能不能过我们先算一笔账。单个数字最大10^9试除法判断一个数是不是质数最坏情况要从2试到√10^9也就是大约31623次。100个数全部判断大约316万次运算。这个数字是什么概念现代CPU每秒能轻松跑上亿次简单运算316万次在C里连零点零几秒都用不到。所以直接用试除法交上去AC没有任何问题。这就是为什么很多题解区的人说“我这题用暴力也过了”。那为什么题目还要叫“质数筛”因为洛谷的题目编排是有教学意图的。你暴力过了不代表你学到了筛法下一次遇到n变成10^6每个数还是10^9试除法就变成了10^9次运算虽然还能扛再下一次遇到让你“筛出2到10^7之间所有质数”的题比如P3383【模板】线性筛素数试除法直接超时超到怀疑人生。P5736的定位就是给你一个“还不需要筛法也能过”的温和场景让你在完全没有性能压力的情况下先把筛法的逻辑学明白。等数据范围变大时你已经有了武器。1.3 一句话总结这题的策略AC保底用试除法学习目标用埃氏筛进阶装可以用欧拉筛。我建议第一次做这题的人三种方法各写一遍分别提交亲眼看看时间和内存消耗的差异。这篇文章后面会把这三种方法全部拆开讲包括代码背后的原理、容易踩的坑以及洛谷提交时的一些真实经验。2. 先把手写质数判断写对试除法的边界细节2.1 最不容易出错的试除写法判断一个正整数x是不是质数教科书定义是大于1的自然数中除了1和它本身以外不再有其他因数。按照这个定义写出来的第一版通常是bool isPrime(int x) { if (x 2) return false; for (int i 2; i x; i) { if (x % i 0) return false; } return true; }这个代码是对的但在x比较大的时候做了很多无用功。一个x如果不是质数那它一定有一个因数小于等于√x。比如数字97你从2试到96在试到2、3、5、7时全都不能整除其实到√97≈9.8也就是试到9就足够了。所以优化版本是把循环条件改成i * i xbool isPrime(int x) { if (x 2) return false; for (int i 2; i * i x; i) { if (x % i 0) return false; } return true; }注意两个细节x 2的判断必须放在最前面因为1不是质数0和负数也不是另外i * i x在x是int类型时当x接近int上限时i*i会溢出所以更稳妥的写法是i x / i既避免溢出又比开平方函数sqrt(x)快得多还不会引入浮点数精度问题。2.2 i*i溢出问题虽然本题不会踩但迟早会踩本题x最大10^9i*i最大也就10^9不会超过int上限约21.47亿所以用i * i写成没问题。但如果你遇到的数据范围是10^12甚至更大比如有些题目要求判断64位整数范围内的质数i*i一旦超过int上限就会变成一个负数或一个奇怪的小数循环条件瞬间失效轻则多跑很多次重则死循环或误判。我见过不少新手在做到“判断long long范围内的质数”时把函数签名改成long long x循环条件却还写着for (long long i 2; i * i x; i)这在多数时候是安全的因为long long能装下更大范围的平方但补一句当x接近9.22×10^18时i*i同样会溢出long long。所以最保险的写法永远是for (long long i 2; i x / i; i)这种写法从底层运算上就杜绝了乘法溢出的可能性。建议从一开始就养成这个习惯省得后面还要回头改。2.3 题目要求用函数就按题目要求来这道题在“函数与结构体”章节里主函数里写一堆逻辑虽然也能AC但编码习惯不好。正确的写法是拆成两层main函数负责读入和输出isPrime函数负责判断。这也是实际工程里的通用思路——一个函数只做一件事。代码组织清晰了调试时定位问题也容易。#include iostream using namespace std; bool isPrime(int x) { if (x 2) return false; for (int i 2; i x / i; i) { if (x % i 0) return false; } return true; } int main() { int n, a; cin n; bool first true; for (int i 0; i n; i) { cin a; if (isPrime(a)) { if (!first) cout ; cout a; first false; } } cout endl; return 0; }这段代码里用了first标记来控制空格输出保证输出结果末尾不会多出一个空格。控制空格这件事虽小但很多面向过程输出的题目都对格式有严格要求养成从第一道题就开始处理空格和换行的习惯后面会省事很多。3. 埃氏筛第一次真正体会“筛”字3.1 筛法的核心思想试除法是一个一个地问“你是质数吗”每次都要从头开始试除费时费力。埃拉托斯特尼筛法简称埃氏筛换了个角度它不判断单个数而是直接把一个区间里的合数全部标记出来剩下没被标记的就是质数。具体做法准备一个布尔数组isPrime初始全部为true先把0和1标成false。然后从2开始如果当前数字i是true说明它是质数就把i的2倍、3倍、4倍……全部标成false。处理完i之后继续往后找下一个未被标记的数。这个过程很像用一个筛子把2的倍数筛掉再筛3的倍数再筛5的倍数……剩下那些怎么都筛不掉的就是质数。数组里存的true和false就成了最终的质数表。3.2 完整实现和关键行解读#include iostream using namespace std; const int MAXN 100000001; bool isPrime[MAXN]; void sieve(int n) { for (int i 0; i n; i) isPrime[i] true; isPrime[0] isPrime[1] false; for (int i 2; i n / i; i) { if (isPrime[i]) { for (int j i * i; j n; j i) { isPrime[j] false; } } } } int main() { int n, a; cin n; sieve(100000000); for (int i 0; i n; i) { cin a; if (isPrime[a]) cout a ; } return 0; }这里有几个关键点第一外层循环只需要到√n。为什么因为任何一个合数m必然存在一个小于等于√m的因子。如果m是一个不大于n的合数那么它一定会在某个i √m √n处被它的那个小因子筛掉。如果外层循环跑完了√n还没被筛掉说明它不存在小于等于√n的因子只能是质数。第二内层循环从i * i开始而不是从2i开始。以i5为例2*510这个数在i2时已经被筛过了3*515在i3时被筛过4*520在i2时被筛过。这些比i*i小的倍数一定包含一个比i小的质因子早就被更早的循环标记过了没必要再筛一遍。从i*i开始能少做很多重复标记虽然时间复杂度不变但常数更优。第三题目中单个数字最大10^9所以这里的isPrime数组要开到10^91吗不需要因为本题其实更适合试除法。埃氏筛在本题的正确打开方式是只筛到输入数据中的最大值。读入时记录最大值maxVal再sieve(maxVal)数组开成maxVal 1大小能省多少算多少。上面代码里我故意写了个10^8的常量是为了说明数组尺寸和内存的关系——10^8个bool大约占100MB很多OJ限制内存128MB所以开10^8勉强能过如果开到10^9直接1GB内存必炸。这就是为什么埃氏筛处理不了10^9级别的区间。3.3 两个容易翻车的地方第一个坑数组初始化。如果你用bool isPrime[MAXN] {false}再想通过一个循环把所有元素改成true没问题但千万别忘了isPrime[0] isPrime[1] false。有人写了循环初始化就把0和1忘了结果输出里混进1WA了还在那查半天。第二个坑内层循环边界。写成for (int j i * i; j n; j i)有个隐藏风险是i*i在i比较大时可能溢出int。在本题数据范围下不会但写成long long j (long long)i * i更保险。或者干脆用for (int j i i; j n; j i)放弃那个小小的常数优化换取绝对安全。3.4 为什么埃氏筛是 O(n log log n)简单推导一下对于每个质数p需要标记n/p个倍数。所以总操作数是n/2 n/3 n/5 n/7 ...也就是n乘以所有不超过n的质数的倒数之和。这个和约等于log log n。所以总复杂度是O(n log log n)。log log n增长极其缓慢。n等于10^6时log log n大约只有2.6n等于10^8时大约3.7。因此埃氏筛在实际运行中几乎可以当成线性看待。这也是为什么很多入门教程敢说“埃氏筛已经完全够用”它的性能对大多数场景确实绰绰有余。4. 想更进一步就学欧拉筛每个合数只筛一次4.1 埃氏筛哪里浪费了埃氏筛虽然快但有个不完美的地方同一个合数会被多个质因子重复筛掉。比如30i2时筛一次i3时又筛一次i5时再筛一次。合数越大质因子越多被重复标记的次数就越多。虽然log log n的常数很小但当n达到10^7甚至10^8时这些无意义的重复标记会白白消耗不少时间。欧拉筛也叫线性筛解决了这个问题它的核心思想是每个合数只被它的最小质因子筛掉一次。4.2 欧拉筛的代码加一行 break 就线性#include iostream #include vector using namespace std; const int MAXN 100000001; vectorint primes; bool isPrime[MAXN]; void linearSieve(int n) { for (int i 0; i n; i) isPrime[i] true; isPrime[0] isPrime[1] false; for (int i 2; i n; i) { if (isPrime[i]) { primes.push_back(i); } for (int j 0; j primes.size() i * primes[j] n; j) { isPrime[i * primes[j]] false; if (i % primes[j] 0) break; } } }这段代码的精华在if (i % primes[j] 0) break;这一行。如果不理解它欧拉筛就是一段背下来但随时会写错的“咒语”理解了它以后再写就不会错。我们来推演一下当i能被primes[j]整除时说明primes[j]是i的最小质因子因为primes是从小到大排列的质数表能整除i的第一个质数就是i的最小质因子。此时如果用下一个质数primes[j1]去乘i得到的合数i * primes[j1]的最小质因子仍然是primes[j]而不是primes[j1]。这个合数应该等到i变大的某个时刻由primes[j]作为筛除因子被处理而不应该现在由primes[j1]抢先筛掉否则以后又会重复标记。所以在这里break掉保证每个合数只被它的最小质因子筛掉一次总操作数为O(n)。用一个具体例子走一遍i6时primes里已经有2、3、5。用2去筛6*212被标为false此时6 % 2 0break。如果不break继续用3去筛6*318但18的最小质因子是2它应该在i9时由2*918被筛掉。现在筛了后面i9时还会再筛一次就重复了。4.3 选埃氏筛还是欧拉筛对大部分竞赛题这两种筛法都能过但实际使用时有各自的场景。这张表是我个人做题时的心得对比维度埃氏筛欧拉筛时间复杂度O(n log log n)O(n)代码长度短逻辑直观稍长需要理解break条件出错概率低中等容易把primes数组和isPrime数组搞混额外功能只有质数表可以顺便维护每个数的最小质因子、欧拉函数、莫比乌斯函数等适用场景求质数本身的多数题目需要最小质因子、积性函数的进阶题目如果你是刚开始学筛法我建议先熟练埃氏筛把它变成肌肉记忆。等做到需要用最小质因子分解质因数、求欧拉函数前缀和这类题目时再上欧拉筛。直接跳过埃氏筛学欧拉筛也可以但前提是你真的理解那行break的含义而不是背模板。对于本题P5736n最大只有100哪怕输入的数字是10^9用欧拉筛筛到10^9也完全不现实。所以本题的最佳实践就是读入时找到最大值用埃氏筛筛到最大值再逐个判断输出。或者干脆用第一节的试除法代码更短。欧拉筛在这里只是为了让你提前接触不是为了AC。5. 洛谷提交的硬经验从空格输出到平台抽风5.1 输出格式空格和换行的小习惯洛谷的评测机对格式的判断有自己的一套逻辑它会把你的输出和标准答案逐字符比对但忽略行末多余的空格和文件末尾多余的换行。也就是说多输出一个行尾空格通常不会判WA而是照常AC。那为什么我还要强调控制空格因为不是所有OJ都这么宽容有些OJ会严格比对比如一些学校的在线评测系统行尾空格就可能导致Presentation Error。与其每次换一个平台就踩一次雷不如从一开始就写规范的输出。一个比较通用的控制空格的写法是bool first true; for (int i 0; i n; i) { if (isPrime(a)) { if (first) { cout a; first false; } else { cout a; } } }这种写法在判断和输出逻辑耦合的场景下用起来比较顺手。如果想要更高级一点可以先把结果存进vectorint res最后统一输出for (int i 0; i res.size(); i) { if (i) cout ; cout res[i]; }第二种写法的好处是判断逻辑和输出逻辑完全分离后续想改成每行输出固定个数、或者输出到文件都很方便。5.2 “无法解析路由对象”这类平台异常的处理思路洛谷的热搜词里经常出现“the route object cannot be resolved”“洛谷提交显示提交失败无法解析路由对象”这类表述。这不是代码问题而是平台自身的偶发异常通常由网络波动、CDN缓存、服务端部署更新等原因引起。我第一次遇到时也慌了一下以为是账号或者代码出问题了后来试了几种方法总结下来比较有效的排查顺序如下现象处理办法提交后提示“无法解析路由对象”先确认代码是否能在本地正常编译运行如果本机没问题基本就是平台问题提示持续出现清一下浏览器缓存或者换成无痕模式再试换浏览器无效切换网络环境比如手机热点排除本地网络DNS缓存的问题以上全部无效过半小时再试平台部署更新或故障恢复后通常会自愈还有一个小经验如果你在洛谷社区里搜问题发现很多人都在同一天反馈同样的问题那大概率是平台方的问题不是你个体的原因。这时候最省心的做法就是等一段时间而不是反复重试反复重试还可能触发平台的提交频率限制造成额外的“提交过于频繁”提示。5.3 用这几道题巩固筛法做完P5736之后如果你想趁热打铁把筛法彻底吃透我推荐按这个顺序刷P3383【模板】线性筛素数模板题数据范围10^8埃氏筛能过但欧拉筛更标准。这道题会强制你写出一个高效的筛法因为10^8的数组和循环对常数很敏感。P1075质因数分解输入一个合数求它的最大质因数。这题用到“一个合数的最小质因子不超过√n”的性质用试除法也能过但配合筛法预处理可以做得更优雅。P3912素数个数数据范围同样是10^8但是求的是个数所以数组可以用bitset或vectorbool来压缩内存。做这题时你会真正体会到内存优化的必要性——10^8个bool要100MB可能踩线但bitset只占12.5MB。我自己刷P3912时一开始用bool数组直接开结果MLE后来换成bitset就过了。这个经历让我记住了“内存和时间的权衡”在实际题目里是真的会遇到的不是书本上的空泛概念。最后分享一点我自己的做题体会说起来有点不好意思我当年第一次做P5736用的是最原始的试除法当时还不知道什么叫“筛”。AC了还很兴奋觉得自己已经会了。直到后面做P3383被一个10^8的数据范围卡到怀疑人生才老老实实回来补筛法。回头再看P5736这题最大的价值不是让你AC而是让你在“暴力还能过”的时候提前接触到筛法的思路。我一直觉得刷题最重要的是“在正确的时间学到正确的东西”——如果这题的数据范围变成10^8你被迫去学筛法那叫“被题目教育了”如果这题数据范围只有100你还是主动去学筛法那就叫“主动成长”。在做题这件事上我建议你多当后者。