信息学奥赛一本通的1410题在OpenJudge上对应的是1.13章节的第21题题目名叫“最大质因子序列”。这道题在两类题库里都收录了属于学会筛法之后“顺手就能做”的典型题目。可奇怪的是很多初学者卡在这里不是因为不会写质数判断而是没想明白“最大质因子”这东西和筛法之间有什么关系。这篇东西我不会只丢一段能AC的代码而是把“为什么这么想、为什么能这么做、常见坑在哪”都拆开讲清楚顺便把这个知识点能延伸出去的套路也一起梳理一下。这道题适合两类人看一类是正在刷信息学奥赛一本通、OpenJudge初级题的选手刷到1.13或者函数/数组章节时遇到这题想弄明白原理另一类是刚学完埃氏筛、想找点简单变式练手的同学。题目本身不难但背后涉及的“用筛法思想维护因子信息”这个技巧后面很多题都会用到。1. 题目到底在说什么1.1 题意与输入输出细节题目原话大概是这样的任意输入两个正整数m和n1 m ≤ n ≤ 5000依次输出m到n之间每个数的最大质因子包括m和n。如果某个数本身是质数就输出这个数自身。输入只有一行两个整数用空格隔开。输出是一行每个整数的最大质因子中间用逗号分隔。注意不是空格这点很关键很多人在输出格式上被坑过。样例输入是“5 10”输出是“5,3,7,2,3,5”。这个样例特别适合用来验证思路因为它覆盖了各种情况5和7是质数输出自己6是2×3最大质因子是38是2的3次方最大质因子是29是3的平方最大质因子是310是2×5最大质因子是5。如果代码能跑对这个样例基本就成功了八九十。1.2 最大质因子到底是什么先明确概念。质因子就是把一个合数分解成若干个质数相乘的形式后参与相乘的那些质数。比如60 2² × 3 × 5那么2、3、5都是60的质因子。最大质因子就是这些里面最大的那个也就是5。特别要注意的是质数本身的情况。比如7它只能分解成7自己所以它的最大质因子就是7。这正好对应了题面里那句“如果某个数本身是质数则输出这个数自身”。有些同学会把质数的最大质因子想成1那是把“质因子”和“约数”搞混了。约数里确实有1但1不是质数所以不可能成为质因子。还有一个容易混淆的点最大质因子不等于“最大的能整除它的质数”那么简单。比如12 2² × 3质因子有2和3最大的是3。但5也是质数5不能整除12虽然5比3大但它不是12的质因子。所以判断一个数是不是质因子前提是这个数要能整除目标数同时它本身必须是质数。1.3 数据范围决定了什么m和n的范围是1到5000这个范围非常小。小到什么程度呢哪怕是每个数都从2到它自己试除一遍做质因数分解计算量也就是每个数最多5000次除法5000个数加起来也就2500万次运算在1秒时限里其实也能过。但问题在于这是一道“筛法教学”性质很浓的题目。它放在一本通的综合应用部分不是为了让你用暴力水过去而是希望你掌握一种更通用的技巧用类似筛法的过程批量维护区间内每个数的某种因子信息。5000这个范围在OJ上属于“怎么折腾都能过”的级别但把n改成500000甚至5000000暴力的思路就会立刻失效而筛法依然活蹦乱跳。所以这道题的正确打开方式不是“我暴力能过就行了”而是借着这个宽松的数据范围把筛法的变式练熟。后面遇到n很大的同类题你才有现成的思考工具。2. 三种思路的对比与取舍2.1 最直观的暴力试除法拿到题最容易想到的思路就是对于区间里的每个数x从x往下找到一个既是质数、又能整除x的数这个数就是最大质因子。写成伪代码是这样for x m to n: for f x down to 2: if (x % f 0 isPrime(f)): print f这个思路确实没错逻辑也很直接。但它的毛病是做了大量重复计算。比如判断f是否是质数在枚举8、9、10的时候都要重新判断2、3、5、7这些数。虽然在这个数据范围内不影响AC但代码如果真这么写评委角度看没问题从学习的角度看少了很多值得琢磨的东西。更关键的是这种双重循环加质数判断的时间复杂度大约在O(n × n × sqrt(n))左右。n是5000时勉强能接受n变成50000基本就快不起来了。所以在信息学竞赛里这种写法只适合用来对拍验证答案不适合当作最终解法。2.2 先筛质数表再暴力试除第二种做法是对暴力做一点优化先用埃氏筛把2到n之间所有的质数筛出来存到一个数组里。然后对于每个数x从小到大遍历质数表如果能整除就更新答案最后剩下的一定是最大质因子。为什么要从小到大而不是从大到小呢因为如果从大到小找找到的第一个能整除x的质数就是最大质因子理论上更快。但我个人建议写从小到大因为这样可以顺便复习一下质因数分解的常规写法。从小到大遍历时每找到一个质因子p就不断用p除x直到除不尽这样得到的质因子是从小到大排列的最后一个被记录的质因子就是最大的。这种写法本质上还是在“试除”只是把“判断f是不是质数”的成本降到了O(1)因为质数表已经预存好了。它的时间复杂度大约在O(n × π(n))其中π(n)是不超过n的质数个数比纯暴力好不少。但思维上依然没有脱离“对每个数单独处理”的框架。2.3 筛法直接更新最大质因子第三种思路就完全不一样了它根本不对每个数单独处理而是用一个数组让整个筛选过程“顺带”把答案算出来。具体做法是这样的开一个数组max_factor初始都是0。然后从2循环到n如果max_factor[i]等于0说明i没有被任何小于它的数标记过那i就是一个质数。此时我们做一次内层循环把i的所有倍数j包括i自己的max_factor[j]更新为i。关键在于内层循环从小到大遍历质数越大的质数越晚执行更新于是会覆盖掉之前记录的小质数。比如6i2的时候会被更新成2i3的时候又会被更新成3最后存下来的就是3。8只能在i2时被更新因为3、5、7都不是8的因子所以它保持2。9在i3时被更新成3。这样一轮结束后max_factor[x]里存的就是x的最大质因子。这个方法有两点特别妙。第一它不用单独判断p是不是质数利用了“合数一定会被更小的质因子标记”这个性质没被标记的一定是质数。第二它用“更新覆盖”代替了“从大到小查找”把每个数被哪个质数整除这个信息在一次扫描里完整记录下来。时间复杂度是经典的O(n log log n)和埃氏筛本身一个量级。空间上只需要一个长度为n1的int数组。这个思路一旦理解了后面求每个数的最小质因子、质因子个数、约数和等一堆题目都能用类似的框架套出来。3. 代码实现与逐行拆解3.1 推荐解法的完整代码基于上面的筛法思路C代码可以写成这样#include cstdio int max_factor[5005]; int main() { int m, n; scanf(%d%d, m, n); for (int i 2; i n; i) { if (max_factor[i] 0) { // i 还没有被任何质数标记过说明 i 是质数 for (int j i; j n; j i) { max_factor[j] i; // 把 i 的所有倍数标记为 i } } } for (int i m; i n; i) { if (i m) { printf(,); } printf(%d, max_factor[i]); } printf(\n); return 0; }这段代码很短但每一行都值得琢磨。数组开成5005而不是5000是因为很多判题系统会允许n取到5000如果数组只开到5000下标就是0到4999访问max_factor[5000]就越界了。开大一点点养成习惯能省去很多调数组越界的痛苦。3.2 用样例模拟运行过程还是用“5 10”这个样例看一下max_factor数组在程序运行过程中的变化。程序从i2开始。此时max_factor[2]是0所以2被判断为质数。进入内层循环j依次取2、4、6、8、10把这些位置都更新成2。循环结束后max_factor[2]、max_factor[4]、max_factor[6]、max_factor[8]、max_factor[10]都等于2。接着i3max_factor[3]是03是质数。内层循环把3、6、9更新成3。注意max_factor[6]原来已经变成2了现在被覆盖成3。这一步就体现了“最大质因子会被更大的质数覆盖”的核心逻辑。i4时max_factor[4]已经不是0了等于2所以不会进入内层循环。这是整个算法高效的关键合数不会作为质数去标记别人因为它在被更小的质因子标记之后就已经“失格”了。同样的i5会把5和10更新成5i7会把7更新成7。i6、8、9、10都已经非0直接跳过。最终数组里max_factor[5]5max_factor[6]3max_factor[7]7max_factor[8]2max_factor[9]3max_factor[10]5。输出时从m到n逐个打印中间用逗号隔开正好得到“5,3,7,2,3,5”。3.3 数组判空的边界问题有人可能会问max_factor[1]怎么办在这个题里m和n都大于1所以1根本不会参与输出。但算法在循环过程中其实也不会处理1。如果某天题目改成了从1开始那max_factor[1]会一直保持0输出就错了。所以如果以后遇到类似的题需要给max_factor[1]单独赋值成1或者特别处理。数组初始化为0这个设定也很有意思。它不只是“初始值”还承担着“是否为质数”的判断功能。这种用同一个数组既存结果又当标记的做法能省一个bool数组初学者看了可能会觉得神奇但不要盲目模仿到所有场景。如果题目要求存的是“最小质因子”就不能用0来当“还没处理”的标记了因为1也不是质数0也有特殊含义通常要另开数组或者用-1初始化。这些细节做题做多了自然会形成条件反射。4. 常见问题与排查技巧4.1 输出格式逗号到底怎么加输出“5,3,7,2,3,5”最后一个数字后面没有逗号。很多第一次提交的同学都在这里栽跟头。最简单的写法是上面代码里的方式在循环里判断只要不是第一个数就先把逗号打出来然后再打数字。这样打出来的结果就是“5,3,7,2,3,5”完全符合要求。也有的同学喜欢把所有结果存到一个字符串里最后一次性输出。这种方法也没问题但我个人觉得在竞赛题里用判断加逗号的方式更轻量省去字符串拼接的开销。尤其当输出量很大的时候频繁拼接字符串反而可能成为性能瓶颈。记住一个原则能在输出时处理格式就不要额外开存储。如果你用的是C的cout也可以这么写for (int i m; i n; i) { if (i m) cout ,; cout max_factor[i]; }逻辑和printf版本完全一样。这里唯一的坑就是别把条件写成i n那样会在所有数字后面打逗号样例输出就会变成“5,3,7,2,3,5,”OJ判的是字符串严格相等哪怕只多一个逗号都会判WA。4.2 数组越界与边界处理数组越界是这种题最容易出的问题。题目说n最大是5000有些同学图省事数组开成max_factor[5000]然后循环到n5000时访问max_factor[5000]数组下标从0开始一共5000个元素合法范围是0到4999访问5000就是越界。虽然大多数时候不会立刻崩溃但结果完全不可预期可能在本地试没问题到OJ上就莫名其妙出错。另外内层循环for (int j i; j n; j i) 这个写法从i开始而不是从2i开始是为了把质数本身也标记上。如果从2i开始那质数自己就永远是0输出质数项时会得到0。所以要记住这种“最大质因子”场景里质数的最大质因子是它自己必须让它被自己标记。边界情况还有m和n相等的时候比如输入“8 8”输出就是“2”。如果m和n相等循环输出只有一个数逗号判断条件i m始终为假正确输出“2”。这个case不算刁钻但能帮你验证代码在短路情况下没有隐藏bug。4.3 合数被误判为质数的风险“max_factor[i] 0说明i是质数”这个推论依赖一个前提循环是从2开始从小到大的。假设i是合数它一定能分解成两个比它小的因子其中较小的那个因子一定是一个小于i的质数。按照算法当外层循环到达那个质数p时内层循环一定会把i标记掉。所以当外层循环到达i时max_factor[i]不可能是0。这个逻辑链很重要但初学者容易忽略它的前提条件。如果把外层循环改成从n往2倒着走这个推论就不成立了因为i是合数时它的质因子可能比i小但还没被处理到。所以在理解这段代码时要时刻记住“从小到大”这个顺序是算法正确性的基石改代码时别顺手把循环方向也改了。我还见过有人为了保险在if里加上is_prime(i)的判断。这样做确实不会错但完全失去了这个写法的优势就退化成2.2节里的“先筛质数再试除”了还多跑了一轮质数判断。建议先理解“0标记即质数”的原理再去决定要不要额外判断。4.4 常见问题速查表我把做这道题时最容易踩的坑整理成一张表没AC的时候可以逐项排查。症状可能原因解决办法输出最后多一个逗号逗号判断条件写反改成if (i m) printf(,);质数对应的位置输出0内层循环从2*i开始没标记自己内层循环从j i开始大数测试时崩溃数组大小不够开到n5或5005输出全是0或乱值外层循环方向写反合数被误判确认循环从2到n递增结果与样例完全不符没理解覆盖逻辑写成取最小值确认用更大的质数覆盖小质数这些都是真实出现过的问题尤其“逗号多一个”和“质数输出0”在OJ提交记录里特别常见。每次看到有人问这道题为什么WA我第一反应都是让他检查这两个位置。5. 从这道题延伸出去的套路5.1 筛法变式的一通百通“最大质因子序列”这道题本质上是在证明一个道理埃氏筛不仅能用来筛出质数列表还能用来维护区间内每个数的某种算术属性。你会了“最大质因子”的更新方式稍微改一改就能解决一大批同族问题。比如求每个数的最小质因子逻辑几乎一样但内层更新时不能直接覆盖要加一个判断条件只有当前位置还没被标记过才赋值。这是因为第一次标记它的质数一定是最小的质数之后遇到的更大质数不应该覆盖它。再比如求每个数的质因子个数。思路是对于质数p把所有p的倍数的质因子计数加1但一个数如果是p的平方、三次方需要计几次这个要仔细想清楚不同的题目要求不一样。如果题目要求去重后的质因子个数那么每个质数p的倍数只加一次因为不管p的指数是多少p这个质因子只算一次。如果题目要求带指数的质因子总数那处理方式就完全不同了。这些变式的核心逻辑都是利用“合数一定会被它的质因子标记”这个性质。只要想清楚更新时机和覆盖规则写起来都不会太费劲。5.2 从最大质因子到质因数分解这道题的另一个价值是帮助你建立“质因数分解”的敏感度。很多数论题的突破口就是把一个数的因子结构看清楚。举个例子判断一个数是否是完全平方数本质上就是要验证它所有质因子的指数是否都是偶数。如果一个数的最大质因子都搞不清楚那谈何指数判断。还有像“找到区间内因子数最多的数”这类题也需要先把每个数分解成质因数才能用约数个数定理去算。所以在学完这道题之后我强烈建议花点时间把“埃氏筛变式全家桶”都自己写一遍最小质因子、最大质因子、质因子个数、约数个数、约数和。写的时候不要抄自己推一遍更新规则。这个过程比刷十道同类题都管用。我就见过一个同学把这几个变式用不同的写法在这道题的框架上练熟了后来做一道要求区间内每个数的最大奇因子的题他几分钟就写出了解法。因为那题本质上就是“最大质因子”的一个变体只是把奇偶条件换了一下。原理通了题目就只是换一层皮。5.3 个人经验写这类题时最容易忽略的点最后分享一个我自己的习惯。每次写完这种筛法变式的代码我不会立刻交而是手动挑几个有代表性的数验证。比如8这种只有一个质因子的6这种有两个质因子且最大质因子不是最大因子的质数11这种只能输出自己的。把这些数放进区间里跑一遍基本就能确认算法逻辑没问题。还有一个印象很深的教训有一年我给别人讲这道题把数组初始化成了全部为1然后判断条件写成了if (max_factor[i] 1)结果1被当成质数标记样例都过不了。虽然这个写法只要把初始值改成0就对了但它让我意识到这类用数组值当标记的写法最怕的就是初始值选得和某个有效答案重合。所以后来我写筛法变式都会特别留意“0、1这两个值在题目里有没有特殊含义”。这道题本身不难但它是“用筛法批量维护因子信息”这条思路的敲门砖。把这篇文章里的代码和原理真正吃透你会发现后面很多数论题看起来题型五花八门骨子里都是这一套东西在变花样。