分解质因数从试除法到素数表优化：C++题解与避坑指南

东华OJ这道进阶题分解质因数我当年刷到的时候差点被名字唬住以为要上什么高深的数论算法结果静下心来拆解之后发现它考察的就是最基础的算术基本定理加一层循环嵌套的功力。C写这道题麻烦点不在数学而在循环边界和输出格式那些容易翻车的小细节。这篇文章完整梳理一遍我的解题思路、代码演变过程和踩过的坑不管你是刚刷OJ的新手还是在准备机试的考研党应该都能从中拿到点能直接用的东西。1. 题目到底在考什么分解质因数的数学本质与隐藏要求1.1 质因数分解与算术基本定理先把这个概念彻底说透。任何一个大于1的正整数都可以唯一地写成若干个质数的乘积而且不考虑顺序时写法是唯一的。比如60 2 × 2 × 3 × 5你会写成60 2^2 × 3^1 × 5^1但本质上还是2、3、5这三个质数撑起了60的全部构成。这个唯一性就是数学里的算术基本定理也是整道题的根。质因数分解之所以在算法题里频繁出现是因为很多数论性质——约数个数、约数之和、最大公约数、最小公倍数——全都可以建立在质因数分解的结果之上。比如说一个数n p1^a1 × p2^a2 × … × pk^ak那它的约数个数就是(a11)(a21)…(ak1)。这道题表面上只让你输出分解式实际上是在为后面一堆数论题打地基。OJ题目的特点就是表面看是一个动作实际考的是你把这个动作做到严谨的能力。分解质因数写起来不过十几行代码但要想不超时、不越界、格式完全正确每一行都需要反复斟酌。1.2 OJ进阶题的位置和考察逻辑东华OJ把这道题放在进阶题里并不是因为它算法难度大而是因为它综合了三个基本功循环控制、整除判断、格式化输出。很多新手写代码单独拿出for循环、if条件、printf输出都会写但组合在一起就出事——要么忘记处理最后剩下的质因子要么在输出星号时多打一个*要么循环终止条件写错导致死循环或者漏因子。这三个能力恰好是机试和笔试中最常被考察的基本盘。所以别看这道题小它背后的考察点非常典型是那种一道题能测出你有没有真正写过代码的题。还有一点进阶题通常还会考察多组数据输入的处理方式。这需要你提前看清楚题目要求是一次输入一次输出还是读到EOF为止不同的OJ风格不一样东华OJ很多题目是多组测试数据写在一个输入文件里的代码要设计成可以循环处理的逻辑。2. 基础解法试除法实现与逐行细节解析2.1 最朴素的试除框架解题思路不需要绕弯子核心就是从小到大试除。我从2开始一个一个质数去试如果当前数字能整除n就说明它是一个质因子把它输出然后用n除以这个因子继续试直到n变成1为止。这个思路很简单但实现时要分清整除和完全分解。举个例子处理数字12时2能整除12输出一个2n变成6此时2仍然能整除6还要再输出一次2n变成3然后2不能整除3了才轮到i3去试。也就是说对同一个因子要用while循环反复除直到除不动为止。很多人第一次写只写了一个if判断结果输出成122×6这种残缺形式这就是没有弄明白一个质因子可以出现多次。代码最直接的写法是这样的#include cstdio int main() { int n; scanf(%d, n); printf(%d, n); int temp n; bool first true; // 控制星号输出 for (int i 2; i * i temp; i) { while (temp % i 0) { if (!first) printf(*); printf(%d, i); first false; temp / i; } } if (temp 1) { if (!first) printf(*); printf(%d, temp); } printf(\n); return 0; }这段代码用了一个技巧i * i temp作为循环终止条件。为什么要这样写因为如果temp还存在一个大于sqrt(temp)的质因子那它一定是独自存在的不可能再配一个同样大于sqrt(temp)的因子否则乘积就超过temp本身了。所以循环结束后如果temp不等于1那它本身必定是一个质数直接输出即可。这步处理极端重要少了它输入17这样的质数时你的输出会变成17然后什么都没了。2.2 循环中变量变化的隐藏逻辑刚接触这道题的人最容易困惑的点在于i * i temp里面的temp是不断缩小的那这个条件会不会出问题我们实际推演一下n 72。初始temp 72。i2时4 72进入while输出2temp变36继续输出2temp变18再继续temp变9。此时224 9还成立但9%2不等于0所以while退出i变成3。然后339 9成立9%30输出3temp变3再试3%30输出3temp变1。此时339 1不成立循环终止。最后temp1不输出。最终结果722223*3完全正确。注意其中的关键点temp在while循环内被不断更新而for循环的终止条件每次都重新计算i * i temp所以当temp缩减到很小时即使i还不大循环也可能提前结束。比如72去掉因子2之后变成9i2时还能继续但i3时处理完9就变成1了循环立刻终止。这种动态边界恰恰是算法高效的关键它避免了无谓的试除。如果换成固定边界写成for (int i 2; i * i n; i)在n2×largePrime这种场景下就会出bug。举个具体例子n2×99991199982使用固定边界n/2时会一直试到447才停下来因为447²199809不超过199982然后在temp已经是99991的情况下后面一堆除数根本除不动纯浪费时间。使用动态temp边界则i只需要试到2就已经处理完了temp此时是99991大于1直接输出。这两种写法性能差距很大在数据量大时直接决定会不会超时。2.3 输出格式处理的两个细节输出格式是这类题目的隐性扣分点。很多人代码逻辑全对就因为多了一个*或者少了换行提交就是Wrong Answer。我使用的方案是维护一个bool first标志。第一次输出因子时不打星号之后每次输出因子前先打印一个*。这样的好处是不管因子出现几次代码都不需要预判这是不是最后一个因子逻辑清晰且不容易出错。还要注意题目要求的输出通常是np1*p2*...*pk的形式等号和乘号前后有没有空格要严格对照题目原文。东华OJ一般没有空格但有些OJ会有格式不符一样判错。所以拿到题第一步不是写代码而是把输出样例抄下来看清楚格式再动手。3. 算法复杂度账本为什么试除法在这道题足够优秀3.1 时间复杂度直观感知与worst case分析很多人一看试除法三个字就觉得这是新手村写法不够高级。但在分解质因数这个场景里试除法的真实复杂度并不是O(n)而是O(√n)量级。核心原因就是一条不需要把所有小于n的数都试一遍只需要试到√temp就能保证覆盖所有可能的质因子。因为如果一个合数n存在某个因子d那么d和n/d中必然有一个不超过√n。这个性质保证了搜索范围极短。但严格地说试除法的最坏情况还是有点表演空间的。假设输入n是一个接近10^9的大质数比如999999937那么i从2一直试到31622约√n才发现除不动等于白白做了三万多轮取模运算。单次运行没问题但如果OJ的测试数据里有一百组这样的大质数三百万次取模也不算轻松——不过说实话现代CPU跑这个量级依然是毫秒级别的事真正的淘汰风险更多来自每组数据都做了大量无谓试除的写法而动态边界的写法已经规避掉了大部分无谓计算。3.2 空间复杂度和实际运行表现这个算法是原地进行的只用了几个整型变量空间复杂度是O(1)哪怕输入的n撑到int极限也不会栈溢出或内存超限。这一点在OJ上非常友好几乎不可能因为内存问题被卡。我实测过一组数据连续分解100000以内所有整数的质因数用动态边界的试除法总耗时大约在50毫秒以内。这个表现说明在绝大多数入门和进阶题里试除法完全够用根本不需要上更复杂的优化方案。所以我的建议很明确先把试除法写熟练、写对再去琢磨优化不要一上来就追求花哨。当然也有场景是试除法压不住的。比如n达到了10^12以上的数量级或者有几百组大质数输入那3万多次循环×几百组就可能真有点慢了。这时候才需要考虑下一章的预处理素数表方案。4. 进阶优化预处理素数表到底值不值得4.1 埃氏筛原理与代码实现用素数表优化的思路是与其让i遍历2到√n的所有整数其中包括大量合数不如提前筛出所有质数只让质数去试除。因为任何一个合数因子它的质因子一定更小所以用质数表按顺序试除效果等价但省掉了对合数的取模判断。素数表的生成用埃氏筛就够了。原理简单说就是从小到大标记合数。从2开始2是质数然后把4、6、8……所有2的倍数全部标记为合数下一个未被标记的数是3它也是质数然后把6、9、12……全部标记以此类推。#include vector std::vectorint getPrimes(int limit) { std::vectorbool isComposite(limit 1, false); std::vectorint primes; for (int i 2; i limit; i) { if (!isComposite[i]) { primes.push_back(i); for (int j i * 2; j limit; j i) { isComposite[j] true; } } } return primes; }使用这个表去分解质因数时只需要循环for (int i 0; i primes.size() primes[i] * primes[i] temp; i)内部逻辑不变。对n999999937这种大质数原来要试31622次现在只需要试3401次质数3401是小于31622的质数个数性能提升接近10倍非常可观。4.2 何时该用素数表一个性价比判断但我也要说句实在话如果这道题只在东华OJ上跑数据量没有那么变态直接用试除法就能过。素数表真正的用武之地是遇到两种情况之一要么是单组数据但n极大且非常抗分解比如RSA那种几百位的大数要么是多组测试数据比如要分解1万个数每个都是10^8量级这时候重复计算质数表的成本被分摊了收益就非常明显。工程上有个经验法则如果测试数据组数超过100组且n的范围上限能被提前知道那预处理上限范围内所有质数是值得的。如果只是三五组数据直接试除反而更快因为筛法的O(nloglogn)预处理开销也不算小为了三四次分解去筛1000000以内的表反而有点浪费。所以这道题真正想考察的能力恰恰是你不仅要会写代码还要能判断够用就行和应该优化的边界。我见过很多人在这一题上强行上线性筛整得代码冗长最后运行效率也没比试除法快多少那就属于用力过猛。5. 踩坑实录OJ提交中的格式与隐藏边界问题5.1 scanf读取失败是隐患吗这道题最常见的一个陷阱是题目可能会给多组测试数据直到EOF结束。很多人误以为只输入一个数写死单次读取结果提交后Wrong Answer。东华OJ的题面通常会在输入描述里写清楚但我吃过的亏就是——做题太急没读题直接写代码。正确的多组写法很简单int n; while (scanf(%d, n) ! EOF) { // 处理一次分解 }如果你用的是C的cin对应写法是int n; while (cin n) { // 处理一次分解 }这里有一个细节值得提醒scanf的返回值是成功读取的变量个数。如果输入结束返回EOF也就是-1循环退出。cin n重载了bool转换操作符读取失败时返回false。两种方式面对多组输入都是安全的。但还有一些零基础教程会让你把EOF理解成文件末尾字符然后写if判断害人。借着这个机会把EOF的含义说清楚它是一个宏本质是-1代表输入流已经结束不是文件里的字符EOF。理解了这一层你就不会在EOF怎么比较这种事情上卡住。5.2 大数和溢出问题再看一个隐蔽的坑i * i temp这一步i和temp都是int类型如果temp接近2^31-1i在循环到大约46340时i*i就已经超过2^31了。好在C的int溢出是定义行为实际是回绕但结果不可靠一旦溢出i*i可能变成负数负数 temp 永远成立循环就不停往下跑直到i溢出又转回正数最终产生不可预料的超时或者死循环。所以如果数据范围没有明确说很小最稳妥的写法是把所有中间量声明为long longlong long n, temp;反正64位整数在现代OJ上几乎不增加运行开销用long long挡掉溢出风险属于白赚的保险。输入输出格式对应改成scanf(%lld, n)或printf(%lld, n)。更极端的情况是n接近0或者负数题目如果没保证n为正整数建议自己加工。负数没有质因数分解的正统意义通常我给出的兜底方案是先输出符号然后对绝对值做分解比如-12 -1 × 2 × 2 × 3。虽然这种处理在题目里大概用不到但写清楚总归严谨。5.3 1这个边界值怎么处理1既不是质数也不是合数它的质因数分解式在数学上定义是空分解。很多题目输入范围写的是正整数不会让你遇到1但万一呢如果你在循环里直接跑temp等于1for条件1*1 1成立初始i2时2*241不成立所以for循环根本不会进入然后temp1判断也不成立最终输出1缺少右侧部分。有的裁判会判格式错误有的会直接忽略这道边界。我的建议是提前把这个分支处理掉if (n 1) { printf(11\n); }这样无论题目数据里藏了什么输出都有明确的右侧值不会被卡格式。虽然实际测试数据大概率不会包含1但写代码的严谨性有时就体现在这种多余的判断里。6. 从这道题延伸出去质因数分解的典型应用与更广阔的算法方向6.1 约数个数、约数和与公约数的快速计算东华这道题拿下了你能立刻把它迁移到好几个经典题目上。第一个是约数个数问题给你n求n的所有正约数个数。如果对每个数都用枚举到√n去数约数那就是O(√n)的暴力但如果你先分解质因数得到 n 2^a × 3^b × 5^c那么约数个数就是 (a1)(b1)(c1)。加一的原因也很直观每个质因子的指数可以取0到a总共a1种组合起来就是总数。第二个是约数和n的所有约数之和等于 (2^02^1…2^a)(3^03^1…3^b)(5^0…5^c)也就是对每个质因子用等比数列求和再相乘。这两个结论在很多数论题里直接用不用反复枚举。第三个是最大公约数和最小公倍数。虽然通常用辗转相除法就够快了但如果你拿到一个数的质因数分解结果公约数问题也可以转化为每个质因子指数的min运算公倍数则对应max运算。这种底层互通的感觉是我觉得质因数分解值得反复刷熟的根本原因。6.2 大数分解的方向Miller-Rabin与Pollards Rho算法如果哪天你遇到的n从10^9涨到了10^18甚至是一个128位的大数试除法和素数表就都撑不住了。这时候经典的进阶方案是Pollards Rho算法配合Miller-Rabin素性测试一起使用。前者用伪随机序列在大概率下快速找到一个大数的一个非平凡因子后者在O(k log n)的复杂度内高概率判断一个数是不是质数。Pollards Rho的思想很有意思它构造一个数列利用生日悖论原理期望用 O(n^(1/4)) 的时间找到一个因子。这里的O(n^(1/4))听起来还是幂级数但对10^18的数来说就是10^4.5量级这在工程上是完全可接受的。不过这个话题展开的话篇幅就失控了。我在这里提它是想说明质因数分解这条技术路线是有纵深感的。你从试除法起步到预处理素数表优化再到Miller-Rabin和Pollards Rho一层层递进知识体系是连贯的。而这一切的起点就是东华OJ这一道进阶题里的十几行基础代码。6.3 这道题对新手还有一层心态训练价值最后从我的实际教学案例说一点体会。我带过的学生里不少人第一次写试除法分解质因数会卡在为什么最后一个temp要单独输出这个点上卡半小时。原因在于他们的思维还停留在在循环里把所有输出做完的定式上没有接受循环结束后剩余部分还需要收尾这种非对称的算法设计。一旦习惯了这种循环处理大部分收尾处理剩余的思维模式后面很多题都会顺畅很多。典型例子如快速排序的partition之后递归处理两侧还有二分查找最后对边界的单独判断本质上都带着类似的逻辑结构。所以每次有人问我这道进阶题到底进阶在哪我的答案都是进阶在让你从埋头写循环升级为跳出循环想清楚整个流程。我个人的建议是刷这道题时别急着一次写对先故意写个错误版本——比如漏掉最后的temp输出或者忘了用while只用了if——然后拿去跑样例观察哪里错了想清楚为什么错了。这个故意犯错-观察-修正的过程对巩固理解比直接抄一遍正确答案有效十倍。另外一个小技巧是写完代码后给自己设计几组特殊测试数据至少包含一个偶数如72、一个奇数合数如45、一个质数如17、一个完全平方数如100、一个大质数如99991。这五组数据跑通了这道题的正确性基本就有保证。这习惯放到所有OJ题上都通用——很多WA问题不是算法错是边界没测到。