企业官网建设流程全解析

东华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，那它的约数个数就是(a1+1)(a2+1)…(ak+1)。这道题表面上只让你输出分解式，实际上是在为后面一堆数论题打地基。

OJ题目的特点就是：表面看是一个动作，实际考的是你把这个动作做到严谨的能力。分解质因数写起来不过十几行代码，但要想不超时、不越界、格式完全正确，每一行都需要反复斟酌。

1.2 OJ进阶题的位置和考察逻辑

东华OJ把这道题放在"进阶题"里，并不是因为它算法难度大，而是因为它综合了三个基本功：循环控制、整除判断、格式化输出。很多新手写代码，单独拿出for循环、if条件、printf输出都会写，但组合在一起就出事——要么忘记处理最后剩下的质因子，要么在输出星号时多打一个"*"，要么循环终止条件写错导致死循环或者漏因子。

这三个能力恰好是机试和笔试中最常被考察的基本盘。所以别看这道题小，它背后的考察点非常典型，是那种"一道题能测出你有没有真正写过代码"的题。

还有一点，进阶题通常还会考察多组数据输入的处理方式。这需要你提前看清楚题目要求，是一次输入一次输出，还是读到EOF为止，不同的OJ风格不一样，东华OJ很多题目是多组测试数据写在一个输入文件里的，代码要设计成可以循环处理的逻辑。

2. 基础解法：试除法实现与逐行细节解析

2.1 最朴素的试除框架

解题思路不需要绕弯子，核心就是"从小到大试除"。我从2开始，一个一个质数去试，如果当前数字能整除n，就说明它是一个质因子，把它输出，然后用n除以这个因子，继续试，直到n变成1为止。

这个思路很简单，但实现时要分清"整除"和"完全分解"。举个例子，处理数字12时，2能整除12，输出一个2，n变成6；此时2仍然能整除6，还要再输出一次2，n变成3；然后2不能整除3了，才轮到i=3去试。也就是说，对同一个因子，要用while循环反复除，直到除不动为止。很多人第一次写只写了一个if判断，结果输出成12=2×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。i=2时，4 <= 72，进入while，输出2，temp变36；继续输出2，temp变18；再继续，temp变9。此时22=4 <= 9还成立，但9%2不等于0，所以while退出，i++变成3。然后33=9 <= 9成立，9%3==0，输出3，temp变3；再试3%3==0，输出3，temp变1。此时33=9 <= 1不成立，循环终止。最后temp=1，不输出。最终结果72=2223*3，完全正确。

注意其中的关键点：temp在while循环内被不断更新，而for循环的终止条件每次都重新计算i * i <= temp，所以当temp缩减到很小时，即使i还不大，循环也可能提前结束。比如72去掉因子2之后变成9，i=2时还能继续，但i=3时处理完，9就变成1了，循环立刻终止。这种"动态边界"恰恰是算法高效的关键，它避免了无谓的试除。

如果换成固定边界写成for (int i = 2; i * i <= n; i++)，在n=2×largePrime这种场景下就会出bug。举个具体例子，n=2×99991=199982，使用固定边界n/2时会一直试到447才停下来（因为447²=199809，不超过199982），然后在temp已经是99991的情况下，后面一堆除数根本除不动，纯浪费时间。使用动态temp边界则i只需要试到2，就已经处理完了，temp此时是99991大于1，直接输出。这两种写法性能差距很大，在数据量大时直接决定会不会超时。

2.3 输出格式处理的两个细节

输出格式是这类题目的隐性扣分点。很多人代码逻辑全对，就因为多了一个"*"或者少了换行，提交就是Wrong Answer。

我使用的方案是维护一个bool first标志。第一次输出因子时不打星号，之后每次输出因子前先打印一个"*"。这样的好处是，不管因子出现几次，代码都不需要预判"这是不是最后一个因子"，逻辑清晰且不容易出错。

还要注意，题目要求的输出通常是n=p1*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::vector<int> getPrimes(int limit) { std::vector<bool> isComposite(limit + 1, false); std::vector<int> 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++)，内部逻辑不变。对n=999999937这种大质数，原来要试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-1，i在循环到大约46340时，i*i就已经超过2^31了。好在C++的int溢出是定义行为（实际是回绕），但结果不可靠，一旦溢出，i*i可能变成负数，负数 <= temp 永远成立，循环就不停往下跑，直到i溢出又转回正数，最终产生不可预料的超时或者死循环。

所以，如果数据范围没有明确说很小，最稳妥的写法是把所有中间量声明为long long：

long 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等于1，for条件1*1 <= 1成立（初始i=2时2*2=4<=1不成立，所以for循环根本不会进入），然后temp>1判断也不成立，最终输出"1="，缺少右侧部分。

有的裁判会判格式错误，有的会直接忽略这道边界。我的建议是提前把这个分支处理掉：

if (n == 1) { printf("1=1\n"); }

这样无论题目数据里藏了什么，输出都有明确的右侧值，不会被卡格式。虽然实际测试数据大概率不会包含1，但写代码的严谨性有时就体现在这种"多余"的判断里。

6. 从这道题延伸出去：质因数分解的典型应用与更广阔的算法方向

6.1 约数个数、约数和与公约数的快速计算

东华这道题拿下了，你能立刻把它迁移到好几个经典题目上。第一个是约数个数问题：给你n，求n的所有正约数个数。如果对每个数都用枚举到√n去数约数，那就是O(√n)的暴力；但如果你先分解质因数，得到 n = 2^a × 3^b × 5^c，那么约数个数就是 (a+1)(b+1)(c+1)。加一的原因也很直观：每个质因子的指数可以取0到a总共a+1种，组合起来就是总数。

第二个是约数和：n的所有约数之和等于 (2^0+2^1+…+2^a)(3^0+3^1+…+3^b)(5^0+…+5^c)，也就是对每个质因子用等比数列求和再相乘。这两个结论在很多数论题里直接用，不用反复枚举。

第三个是最大公约数和最小公倍数。虽然通常用辗转相除法就够快了，但如果你拿到一个数的质因数分解结果，公约数问题也可以转化为每个质因子指数的min运算，公倍数则对应max运算。这种底层互通的感觉，是我觉得质因数分解值得反复刷熟的根本原因。

6.2 大数分解的方向：Miller-Rabin与Pollard's Rho算法

如果哪天你遇到的n从10^9涨到了10^18，甚至是一个128位的大数，试除法和素数表就都撑不住了。这时候经典的进阶方案是Pollard's Rho算法，配合Miller-Rabin素性测试一起使用。前者用伪随机序列在大概率下快速找到一个大数的一个非平凡因子，后者在O(k log n)的复杂度内高概率判断一个数是不是质数。

Pollard's Rho的思想很有意思：它构造一个数列，利用生日悖论原理，期望用 O(n^(1/4)) 的时间找到一个因子。这里的O(n^(1/4))听起来还是幂级数，但对10^18的数来说就是10^4.5量级，这在工程上是完全可接受的。

不过这个话题展开的话篇幅就失控了。我在这里提它，是想说明：质因数分解这条技术路线是有纵深感的。你从试除法起步，到预处理素数表优化，再到Miller-Rabin和Pollard's Rho，一层层递进，知识体系是连贯的。而这一切的起点，就是东华OJ这一道"进阶题"里的十几行基础代码。

6.3 这道题对新手还有一层"心态训练"价值

最后从我的实际教学案例说一点体会。我带过的学生里，不少人第一次写试除法分解质因数，会卡在"为什么最后一个temp要单独输出"这个点上卡半小时。原因在于他们的思维还停留在"在循环里把所有输出做完"的定式上，没有接受"循环结束后剩余部分还需要收尾"这种非对称的算法设计。

一旦习惯了这种"循环处理大部分，收尾处理剩余"的思维模式，后面很多题都会顺畅很多。典型例子如快速排序的partition之后递归处理两侧，还有二分查找最后对边界的单独判断，本质上都带着类似的逻辑结构。所以每次有人问我"这道进阶题到底进阶在哪"，我的答案都是：进阶在让你从"埋头写循环"升级为"跳出循环想清楚整个流程"。

我个人的建议是，刷这道题时，别急着一次写对，先故意写个错误版本——比如漏掉最后的temp输出，或者忘了用while只用了if——然后拿去跑样例，观察哪里错了，想清楚为什么错了。这个"故意犯错-观察-修正"的过程，对巩固理解比直接抄一遍正确答案有效十倍。

另外一个小技巧是，写完代码后给自己设计几组特殊测试数据，至少包含：一个偶数（如72）、一个奇数合数（如45）、一个质数（如17）、一个完全平方数（如100）、一个大质数（如99991）。这五组数据跑通了，这道题的正确性基本就有保证。这习惯放到所有OJ题上都通用——很多WA问题不是算法错，是边界没测到。