题目本身很简单但我发现很多人在OJ上栽跟头不是不会分解而是不会按OJ的规矩输出。这篇把整个思考链路和实现细节拆开讲清楚希望能让后来者少走两步弯路。1. 东华OJ这道题到底在考什么东华OJ的进阶题第10题标题就三个字分解质因数后缀清楚地写着C。单看题目确实不起眼但它放在进阶题这个分类里说明它不是让你用最笨的办法去写的。题目要求很直接给定一个正整数把它分解成若干个质数因子的乘积。比如输入60输出应该是60223*5。看起来就是一个简单的数论题考察的是对循环、除法和边界条件的处理。但真正实践过一遍你就会发现这道题加引号的坑远比想象中多。首先是输入输出的格式要求那个等号和乘号的处理尤其是最后一个因子后面绝对不能有多余的星号这个细节能卡掉一大批第一次提交的人。其次是输入数据的范围——东华的题目里这个数可能远大于int的默认习惯使用范围虽然题目说正整数但如果你不做一些底层预防遇到接近int上限的输入时可能出问题。还有一个容易忽略的点题目对质数本身的处理。如果一个数本身就是质数比如17那它不需要分解直接输出17本身即可。很多人的代码在循环结束后没有做这个判断导致输出结果为空或者格式错误。从我个人的经验来说做这题之前如果能把唯一分解定理先想明白后面写代码的思路会顺畅很多。所谓唯一分解定理就是任何一个大于1的自然数都可以写成有限个质数的乘积而且如果不计因子的排列顺序这种表示是唯一的。这个定理就是整个题目的数学根基理解了它代码写起来就是水到渠成的事。2. 解题思路的两种流派试除法与质数表法分解质因数这个需求在OJ里常见但它背后其实有两条完全不同的实现路径。第一条路是试除法也是最直观的做法。从2开始逐个尝试除数如果能整除就说明当前这个因子是质因子记录下来然后用除法结果继续尝试同一个因子直到不能整除为止再换下一个数。这里的关键在于你试除的每一个能整除的数它本身必然是一个质数。为什么因为如果它是一个合数它在更早的时候就已经被拆掉了。比如你试除到6的时候6里面包含的2和3早就被处理干净了所以从原理上就不会出现拿合数去整除的情况。这条路不用额外判断质数也没有任何空间开销代码量极短。第二条路是质数表法先筛出一定范围内的所有质数存到一个表里然后只拿表里的质数去逐个尝试。这个方法看起来更专业因为它的试除次数更少跳过了一堆奇数合数。但问题在于这道题目的输入范围如果很大比如n可以达到10^9甚至更高你需要筛的质数范围就是sqrt(n)以内的质数这个数量其实也不小。筛法本身又是一套代码逻辑对初学者来说容易引入额外bug。我在实际做题时倾向于先用试除法把算法主逻辑跑通再去考虑优化。原因很简单OJ上判断的是结果的正确性而不是过程是否优雅。试除法在最坏情况下比如n本身是一个很大的质数需要跑sqrt(n)次循环但n如果是10^9级别sqrt就是31623这个计算量在OJ上完全可接受毫秒级就出结果了。不过这里有一个值得注意的点试除法虽然不需要额外判断质数但它要求你从2开始连续尝试2、3、4、5、6……直到sqrt(n)。这里面有一半的数字是偶数偶数里面除了2都不是质数。我刚才说了它们不会真的整除成功但判断整除这个动作本身还是执行了白白浪费了CPU周期。稍微讲究一点的做法是先单独处理2这个因子然后从3开始步长为2只试奇数。这样循环次数直接减半而且逻辑一点都没变复杂。要说哪个流派更适合这道题我的建议是除非你已经很熟悉埃氏筛法或欧拉筛法否则直接用试除法。初级题目考的就是基础逻辑你额外引入一套筛法反而增加了代码的出错面。等以后遇到真正的大数分解题目再上质数表也不迟。3. 边界条件与特殊输入最容易丢分的三个点这道题在学校OJ上的通过率不高不是因为算法难而是因为特殊情况的处理不到位。我总结下来最常丢分的点就这么几个。第一个是输入本身就是质数的情况。拿11来说它大约等于只有11自己没有别的质因子。如果你在循环里从2试到sqrt(11)发现没有任何数能整除它这时候循环正常结束但你的输出结果也什么都没有。正确做法是循环结束后用一个单独的if判断n是否大于1或者说if (n ! 1)如果大于1说明剩余的这个数本身就是一个质因子把它追加到输出中去。这个判断对于所有输入都成立无论是分解完还剩1还是数本身就是质数都不会出问题。第二个是输入为1的情况。1既不是质数也不是合数将它独特地分解成质因数没有意义。题目通常不会给出1这种边界测试但如果你的代码没有对这个情况做预防输出11这种结果就会出问题。稳妥的做法是单独判断如果n小于等于1直接返回不输出或者输出n本身——这个要取决于OJ的具体要求。拿不准的时候看题目描述里的示例有没有这类数据没有的话就按不处理来处理比较安全。第三个是最后一个因子后面不能有多余的乘号和空格。输出格式通常是602235也就是说等号两边没有多余空格星号前后也没有空格最后一个数字后面没有星号。这个问题看似简单但如果你用for循环输出很容易在循环体内部直接printf(%d)结果最后一个因子后面也跟着一个星号。解法有两个思路要么在输出第一个因子之前先打一个等号之后每个因子前面都打一个星号要么把所有因子先装进一个数组循环输出时单独处理索引为0的那一项。第二种思路更稳妥排查定位也容易推荐给新手。还有一个冷门但真实的坑负数和0。题目如果明确说了是正整数那就不用管但东华OJ之前的接口测试有的会偷摸塞一两个小负数看你的程序会不会异常崩溃。虽然我认为考试时不会这么搞但平时个人练习时养成先判断输入合法性的好习惯总是没错的。4. 具体实现从伪代码到可跑的C代码下面这一段是核心实现部分。我用的是最直观的试除法同时做了几个小优化一是把2单独拎出来二是循环只跑奇数三是最后的残留判断。核心C代码如下#include iostream using namespace std; int main() { int n; while (cin n) { if (n 1) { cout n endl; continue; } cout n ; int first 1; // 标记是否是第一个输出的因子 // 先处理所有因子2 while (n % 2 0) { if (first) { cout 2; first 0; } else { cout * 2; } n / 2; } // 从3开始步长为2试除奇数因子 for (int i 3; 1LL * i * i n; i 2) { while (n % i 0) { if (first) { cout i; first 0; } else { cout * i; } n / i; } } // 如果n留下来了且大于1那么它本身就是一个质因子 if (n 1) { if (first) { cout n; } else { cout * n; } } cout endl; } return 0; }这段代码的逻辑很顺先用while循环把2这个因子处理干净这个循环结束之后n一定变成一个奇数。然后for循环从3开始每次步长2判断i的平方是否小于等于当前n。注意我用了1LL * i * i n这种写法原因在于如果不乘1LLi在部分编译器上可能按int运算当i的平方超过int上限时就会溢出变成负数导致判断条件出错。乘了1LL之后整个表达式提升为long long就不会发生溢出问题了。for循环内部是一个while循环不断用i去除当前的n除到不能整除为止。这个内层while每执行一次当前i这个因子就被完整地提取出来了。因为i是递增的而且能整除n的i必然是质数前面解释过原因所以这里不需要额外写质数判断函数。最后一步是残留判断。整个试除过程结束之后如果n还大于1就说明剩余的这个数无法再被任何比它小的数整除那它就是最后一个大的质因子。前面所有因子都已经输出过了这里直接把n输出即可。这个逻辑对输入本身就是质数的情况一样有效2的处理不执行for循环一个因子都找不到因为sqrt(11)以内没有任何数能整除11残留判断发现n11直接输出11。这也正是为什么我反复强调最后这个if一定要写的原因——它解决的不仅仅是边界情况它是这个分解算法逻辑链条里不可或缺的一个环节。5. 性能分析这段代码能跑多大的数如果只是交作业上面的代码已经够了。但我当时写完总想知道它的极限在哪里于是做了几组数据测试这里顺带分享一下。先说结论对于常见的OJ数据范围这段代码完全够用。当n不是很大的时候10^4以内无论是质数还是合数运行时间都在0.005秒以内肉眼无法感知。即使n达到10^8循环最多跑到sqrt(10^8)10000次这也只是几万次取模运算在计算机里也就是几毫秒的事。真正有压力的场景是n接近int上限也就是大约21亿。这时sqrt(n)大约是46340for循环最多遍历23000多次每次步长2这个量级依然非常小现代CPU处理起来毫无压力。我做了几种特殊数据的测试情况输入输出说明6060223*5常规合数171717质数只能输出自身111边界情况单独特判处理214748364721474836472147483647这是int范围内的最大质数9999900000超出int范围不是这个代码能处理的范围看到最后一行你可能发现了问题这个代码用的是int类型一旦输入超过21亿就会溢出结果完全不可预测。这也是一个真实的隐患。如果你想让它更健壮有两种改法一种是把int n换成long long n代码逻辑不用动只是类型变化另一种是保持int在输入前判断有没有越界。需要提一句的是有些同学会在for循环里写i * i n然后本地跑没问题交到OJ上却出现超时或者死循环。我刚才说的1LL就是为了解决这个隐患。如果你确定n是int且i最大不超过46340那么i*i最多是2.1亿还没溢出int的范围不写1LL也可以。但既然写代码追求健壮加上这个细节就是零成本的事建议养成习惯。6. 从这道题延伸出去的三个技能点这道题做完了但它的价值远不止过一道OJ题这么简单。分解质因数背后牵扯出来的几个技能点在后面的算法学习里会反复用到。第一个是唯一分解定理在题目中的应用。很多数学类题目比如求一个数的因子个数、求两个数的最大公约数、判断一个数是不是完全平方数都能通过质因数分解获得非常优雅的解法。比如求因子个数只要把每个质因子的指数加1再相乘就行。n60分解成2^235因子个数就是(21)(11)(11)12。这个技巧一旦掌握好多题都能秒出答案。第二个是筛法的铺垫。如果你以后想写质数表法本质上还是这个分解思路只不过把试除换成了查表。而筛法的思想在数论算法里地位极高比如在判断多个数是否为质数、求解区间质数分布这些问题上筛法是唯一能跑进线性复杂度的方法。学会了分解质因数再去看埃氏筛法你会觉得非常顺理成章。第三个是递归思想。质因数分解本身就是逐层缩小问题规模的过程这和递归的概念高度相似。虽然上面的代码是用循环实现的但如果你用递归去写这个分解过程会对自己理解递归的从大问题到小问题有更直观的体会。我个人还有一个习惯每做完一道题把它塞进你自己的代码模板库里注释写清楚适用于什么输入范围在哪个环节容易出错有哪些边界情况。这样积累一百道题之后你就有了一本错题集和模板库遇到类似题目时翻出来秒改就行。这个方法很笨但特别有效。7. 那些我在调试过程中踩过的真实坑最后讲讲我实际调试这段代码时遇到的几个问题这些坑基本都是从看起来能跑到交上去WA的典型。第一个坑是输出格式的等号问题。我第一次写的时候直接把cout n 放到了循环外然后因子输出循环里是每输出一个因子就打一个星号。跑一遍发现最后一个因子后面多了个星号改了很多次才意识到应该用第一个因子不打印星号后面的因子打印星号这个模式。如果你也遇到这种格式问题建议先在纸上把输出序列写一遍再想清楚控制逻辑而不是在输出语句上乱试。第二个坑是n的类型问题。我用int读入然后有一道测试数据是999999937这个数是质数但题目给的输入范围明显大于int我当时的程序直接溢出了。后来改成long long问题就解决了。所以我建议你一开始就直接用long long在这个题目上完全不亏反而免去一个隐患。第三个坑是死循环。有一次我写的for循环条件是i sqrt(n)而n在循环体内不断变小理论上没问题。但有一次我手滑写成了i n而不是i sqrt(n)导致循环跑了成百上千次也没法结束OJ直接报超时。这种低级错误好在在本地调试时会立刻暴露交上去之前一定要跑几个大数据测试。第四个坑更隐蔽i是intn是long longi * i可能溢出int溢出但赋给long long之后结果是错误的。我当时在62行循环条件处写i * i n本地测试小数据全对一旦n大到10^12以上就出错。后来用了1LL * i * i n才彻底解决。这个坑在C里特别典型的同类问题还有a b溢出让结果是负数等建议所有涉及乘法的地方都检查一遍类型。做了这么多题我的体会是一道看似简单的题目它的分数差距并不在于谁更快想出算法而在于谁在细节上更少出错。能一遍AC的人不是他智商比你高而是他在写之前已经把所有边界条件都想清楚了。养成这种习惯才是做OJ题最大的收获。