企业官网建设流程全解析

1. 题目理解：这道“进阶题”到底在考什么？

如果你刷过东华OJ的进阶题，大概率会遇到这道“分解质因数”。题号排在第10位，名字不花哨，但很多人在它上面卡过。我第一次做的时候也觉得简单，无非就是把一个数拆成质数相乘，后来才发现“拆完”和“拆对”是两码事，尤其面对多组输入、输出格式、边界数据时，稍微大意一点就是WA。

1.1 质因数分解的数学基础

质因数分解其实是一个非常经典的数论概念：任何一个大于1的正整数，都能唯一地表示成若干个质数的乘积，而且不考虑顺序时写法唯一。例如：

12 = 2 × 2 × 3
60 = 2 × 2 × 3 × 5
100 = 2 × 2 × 5 × 5

这个结论叫“算术基本定理”，也是唯一分解定理。它听起来像废话，但几乎所有关于整除、约数、最大公约数的问题，最后都能追回到质因数分解上去。拿这道题来说，它不要求你证明定理，而是要求你切实地“把一个数拆干净”。

很多同学一看到“质因数”三个字，第一反应是先去写一个判断质数的函数，然后再去遍历所有数字，判断哪些是质因数。这样做不是不行，但绕了很大的弯路。分解质因数的关键不在于“判断质数”，而在于“吃掉因子”：每找到一个能整除当前n的数i，就要把n里所有的i全部除掉，然后继续处理剩下的部分。这才是算法上的核心思路。

1.2 东华OJ这道题究竟要求什么

东华OJ的输入一般是一个正整数n，输出要求形如：

12=223
7=7

也就是等号左边是原数，右边是它的质因数乘积，因子从小到大排列，乘号用英文星号*表示。题目如果要求“按从小到大的顺序”，实际就是在告诉你：质因数不能乱排，必须严格递增或按重复次数排列。比如60必须输出60=2*2*3*5，不能输出60=3*5*2*2。

这个输出格式是一个典型的OJ隐藏考点。很多人算法写对了，但因为等号后面没换行、乘号前多了一个空格、最后一个因子后面多打了一个*，照样拿不到分。所以处理这道题时，除了要会算，还要把输出格式当成核心需求一样认真对待。

1.3 “进阶”两个字体现在哪里

如果仅仅是判断质数，很多同学在刚学循环时就会了。但“分解质因数”把好几样东西放在了一起：循环嵌套、数论基础、边界处理、输出格式控制、多组数据处理。而且它还是后续很多题目（约数个数、约数和、欧拉函数、同余问题）的基础组件。

比如你现在学会了分解质因数，后面遇到“求n有多少个约数”的题，就能直接用分解结果来计算。也就是说，这道题表面上只是刷题列表里的一小题，实际上是在帮你建立一个数学转换工具。理解了这一点，你就明白为什么OJ要把它放进进阶题里，而不是放在最基础的“求质数”题目里。

2. 算法设计：为什么试除法够用，以及一定要除到√n

2.1 最直观的试除法：模拟手算过程

不考虑任何优化，最本能的写法是：从2开始，从小到大依次枚举可能的除数i，只要n能被i整除，就输出一个i，并把n除以i，然后继续用i去试，直到n不再能被i整除，再把i加1。

举个例子，n=60时这个过程是这样的：

60能被2整除，输出2，n变成30；30还能被2整除，输出2，n变成15；15不能被2整除，i变成3；15能被3整除，输出3，n变成5；5不能被3整除，i变成4，不行；i变成5，5能被5整除，输出5，n变成1，结束。

结果就是60=2*2*3*5。这个算法非常符合人的手算直觉，代码写出来也很短。它的正确性依赖一个事实：任何合数n至少有一个小于等于√n的质因子，所以只要从小到大试，就一定能先找到最小质因子，再递归地处理剩余部分。

2.2 为什么只需要试到√n

这是这道题最重要的优化点。如果n有一个大于√n的因子a，那么它的配对因子b = n/a一定小于√n。换句话说，因子是成对出现的，比如24的因子对是(1,24)、(2,12)、(3,8)、(4,6)，左边一个不超过√24≈4.9。

所以在试除过程中，如果从2一直试到√n都没有找到能整除n的数，那么n本身就是质数，不需要再继续试下去了。最典型的例子是n=17，√17≈4.12，试2、3、4都不能整除，这时就可以直接断定17是质数。如果傻乎乎地从2试到16，等于白白多算了三倍以上的循环次数。

在代码里，循环条件一般写成i <= n / i或者i * i <= n。注意这里不要写成i < n，否则一方面效率低，另一方面也违背了“因子成对”的数学性质。

2.3 循环条件里的n是“动态”的

这里藏着一个非常经典的坑。很多人会把循环上界提前算好，写成像这样：

int limit = sqrt(n); for (int i = 2; i <= limit; ++i) { ... }

这种写法在少数情况下能碰巧过，但逻辑上是不严谨的。因为在分解过程中，n会不断变小，每次除完一个因子后，新的n对应的√n也会变小。比如n=100，一开始上限是10，但当你把质因数2提出来之后，n变成了25，这时候理论上只需要试到5就够了，没必要继续试到10。虽然多试几次结果不一定出错，但会让算法变得冗余，甚至在某些特殊数据下出现漏判或多余操作。

正确的做法是让循环条件实时依赖当前的n，也就是写成：

for (int i = 2; i <= n / i; ) { ... }

这样每循环一次，都会用最新的n去判断是否继续。虽然代码只差了一点点，但背后的数学思想完全不一样：你是在和不断缩小的“待分解数”打交道，而不是盯着一个固定不变的原始数字不放。

2.4 先处理2的小优化：循环次数直接减半

在所有质数中，2是唯一一个偶数。所以可以先把n中所有的因子2全部提取出来，然后从3开始，每次让i加2，跳过所有偶数。这样一来，循环次数大约减少一半。

比如输入1000003，如果从2一路试到1000002，要吃不少时间；而加上√n限制后，最多只需要试到1000左右，再跳过偶数，实际循环只有500次左右，几乎瞬间完成。虽然东华OJ这道题的n范围不一定那么大，但这种优化思路非常值得养成。你可以把它理解为“把已知的常识变成代码里的条件”，2以外的偶数都不可能是质数，就不用浪费时间去做除法了。

这段优化不是必须的，但它能让你从“能过题”走向“会优化”。在刷OJ的过程中，很多题目考的就是这种“比别人多想一步”的能力。

3. C++实现：从零开始写一份能AC的代码

3.1 函数怎么设计：直接打印还是返回结果

这道题本质上只要求输出，所以最自然的做法是写一个void函数，在函数内部完成分解和打印。但如果你想为后续的题目积累工具，也可以设计成返回vector<pair<int, int>>，其中每个pair表示“质因子i出现了多少次”。我个人建议先从直接打印的版本开始，把逻辑跑通后，再扩展成通用版本。

把分解逻辑单独抽出来还有一个好处：main函数会非常干净，只负责读取输入和调用函数。当OJ要求多组数据输入时，这个结构能让你少犯很多低级错误。

3.2 一份可以直接提交的C++代码

下面这份代码是我实际在东华OJ上测试过的写法，没有用到任何花哨的库函数，完全依赖循环和除法。

#include <iostream> using namespace std; void decompose(int n) { if (n == 1) { cout << "1=1" << endl; return; } cout << n << "="; bool first = true; for (int i = 2; i <= n / i; ) { if (n % i == 0) { if (!first) { cout << "*"; } cout << i; first = false; n /= i; } else { ++i; } } if (n > 1) { if (!first) { cout << "*"; } cout << n; } cout << endl; } int main() { int n; while (cin >> n) { decompose(n); } return 0; }

代码核心分成三步。第一步，处理n=1的特殊情况，因为1没有质因数，但题目如果输入1，你至少要输出1=1才符合等号两边相等的语义。第二步，从小到大枚举i，只要i能整除n，就输出一个i并把n缩小，直到不能整除为止。第三步，循环结束后，如果n仍然大于1，说明它是一个还没来得及输出的质因子，直接追加到末尾就行。

3.3 为什么写i <= n / i而不是i * i <= n

这是一个很多新手都会踩的坑。i * i <= n在数学上完全正确，但在C++里存在整数溢出风险。当n接近int上限2147483647时，i只要超过46340，i * i就会超出int能表示的范围，变成负数，循环判断直接失效。

换成i <= n / i可以完美避开溢出，因为除法不会超过int的范围。这种写法在竞赛里非常常见，它不依赖64位类型也能保证安全。如果你实在喜欢i * i的写法，至少写成1LL * i * i <= n，用long long临时运算，但说实话不如n / i干净。

3.4 输出格式的几个经典坑

• 等号左边是原数，右边是分解式，中间不要加空格，除非题目明确要求。
• 乘号是英文星号*，不是字母x，也不是中文乘号。
• 第一个因子前不能输出*，最后一个因子后也不能输出*。
• 每行结束要换行，多组输入时每组输出占一行。

我用一个bool first标记来解决第一个因子的问题。初始为true，第一次输出因子时不打印乘号，随后把first改成false，之后每次输出因子前都先打印一个*。这个技巧在输出逗号分隔、空格分隔时同样适用，属于竞赛基础技能。

3.5 如果题目要求输出指数形式

有些变体题会要求把输出写成60=2^2*3*5，也就是相同质因子合并成指数形式。这种改动也很容易实现，核心是把“每找到一个因子立刻输出”改成“先数一下相同因子出现了几次，再一次输出”。

void decomposeExp(int n) { if (n == 1) { cout << "1=1" << endl; return; } cout << n << "="; bool first = true; for (int i = 2; i <= n / i; ++i) { if (n % i == 0) { int cnt = 0; while (n % i == 0) { n /= i; ++cnt; } if (!first) { cout << "*"; } if (cnt == 1) { cout << i; } else { cout << i << "^" << cnt; } first = false; } } if (n > 1) { if (!first) { cout << "*"; } cout << n; } cout << endl; }

这段代码体现了一个很重要的解题思路：先处理共性逻辑，再根据具体要求调整输出格式。算法本身的骨架没有变，变的只是“如何表达结果”。这也是为什么我说分解质因数是个基础能力，而不是一道孤立的小题。

4. 调试、测试与常见问题

4.1 用边界数据自测，比跑十个随机数都有用

很多人在本地测试时只跑题目给的样例，样例过了就直接交，结果WA。分解质因数这道题，我建议你至少测下面这一组边界数据。

尤其是最后一项，如果一个数本身是质数，优化版本只试到约1000就能结束，而暴力写法可能要循环到99万次。这组数据一测，就能明显感受到算法优化的威力。

4.2 最容易犯的三个错误

第一个错误是忘掉在while循环里把n缩小。比如写成if (n % i == 0) { cout << i; }，内存循环没有n /= i，结果就是同一个因子被无限打印，程序卡死。记住，每找到一个因子，就必须把n“吃掉”一部分，让问题规模变小。

第二个错误是把循环条件写成i * i < n，少了一个等号。比如n=4时，i=2时i * i恰好等于4，如果用<判断，循环直接不进去，最后输出4=4，答案错误。这个等号问题非常隐蔽，样例一般测不出来。

第三个错误是输出顺序不对。比如先把*打印出来再判断是不是第一个因子，结果第一项前面多了一个星号。这种格式错误在OJ判定里就是WA，不会因为“算法对”就放过你。

4.3 从“能过样例”到“能AC”：自测清单

除了跑上面的表格，我还会做一个更稳妥的测试：用暴力法做对照。写一个最简单的分解函数，从2一直试到n，虽然慢但绝对正确，然后随机生成大量小数字，让优化版本和暴力版本的结果逐一对比。这个方法虽然土，但能抓出90%的隐藏bug。

对于这道题，你还可以刻意测试所有小于等于100的正整数，把它们的输出结果全部打出来，人工瞄一眼格式。我当年就是这么干的，虽然看起来很笨，但确实帮我发现了n=1时没有输出的严重问题。

4.4 OJ常见报错排查速查表

如果出现Time Limit Exceeded，先检查是不是把i <= n / i写成了i <= n。如果出现Wrong Answer，优先检查输出里的等号、乘号、换行。如果这两项都没问题，再检查n=1和质数输入。

4.5 多组输入和换行的处理

东华OJ这类在线判题系统，经常把多条测试数据放在同一个输入文件里，要求程序全部处理完。最稳妥的做法就是用while (cin >> n)来读，读到文件末尾自动结束。千万不要只读一次n就跑，否则只有第一组数据能过。

使用cin的好处还在于它会自动跳过空白字符，包括空格、换行和Tab。你不需要手动处理\n带来的残留问题，代码会干净很多。如果用scanf，也要注意格式字符串的写法，避免漏掉换行符。

5. 从这道题延伸出去的几个方向

5.1 质因数分解是很多数论题的前置技能

学完分解质因数之后，你会发现好多题都能从这里接到线。比如说，一个数的约数个数可以通过它的质因数分解直接算出来。n = p1^a1 * p2^a2 * ... * pk^ak，那它的约数个数就是(a1+1)(a2+1)...(ak+1)。举个例子，60 = 2^2 * 3^1 * 5^1，约数个数就是(2+1)(1+1)(1+1)=12，正好对应1、2、3、4、5、6、10、12、15、20、30、60这12个约数。

约数和、最大公约数、最小公倍数、欧拉函数等概念也都能从质因数分解的角度重新理解。所以你现在写的这几十行代码，未来会被反复利用。这也是我强烈建议你把它封装成函数的原因——以后遇到新题直接复制过去改改就行。

5.2 递归写法：另一种理解方式

分解质因数还可以用递归来实现。思路是：找到n的最小质因子i后，输出i，然后递归分解n/i。终止条件是n变成1，或者n本身是质数时直接输出它。递归版本代码更短，但需要注意输出格式，而且对于int范围内的n来说递归深度完全够用，不用担心栈溢出。

不过我个人在OJ上更推荐迭代写法。递归虽然代码优雅，但每次递归都会产生函数调用开销，而且格式控制容易出错。在学习递归时，你可以拿这道题来练手，但在追求稳定AC的阶段，迭代是更可靠的选择。

5.3 多次查询时：用质数表加速

如果题目升级成“输入T组n，每组输出质因数分解”，你再对每个n都从2开始试除，就会重复做很多无用功。更好的做法是先用埃氏筛，把[2, √maxN]范围内的所有质数一次性筛出来，然后只拿这些质数去试除n。这样既可以跳过所有合数，又能处理大量查询。

埃氏筛的核心思想很简单：从2开始，把每个质数的倍数全部标记为合数。代码大概长这样：

vector<bool> isPrime(maxN + 1, true); isPrime[0] = isPrime[1] = false; for (int i = 2; i * i <= maxN; ++i) { if (isPrime[i]) { for (int j = i * i; j <= maxN; j += i) { isPrime[j] = false; } } }

筛完之后，把isPrime里为true的下标收集到一个vector<int> primes里，分解时只遍历这个质数表。这个优化思路在东华OJ的进阶题和更高难度的算法题里非常常见，属于从“会分解一个数”到“会处理一批数”的关键一步。

5.4 如果n非常非常大呢

当n达到10^18级别时，试除法就不够用了，需要借助Pollard-Rho算法和Miller-Rabin素性测试。这些算法属于竞赛进阶内容，东华OJ的基础题大概率不会涉及。但理解它们存在的原因是必要的——算法复杂度决定了你能处理的数据范围。试除法是O(√n)，Pollard-Rho的期望复杂度则快得多。先掌握好试除法和筛法，再一步步往上走，这样知识体系才稳固。

5.5 一个小技巧：先让思路跑通再写代码

最后分享一个我自己的做题习惯。拿到这种“看起来很简单”的题，先不要急着打开编辑器敲代码，而是拿纸笔把n=60的分解过程写一遍，看自己手算是怎么做的，代码就照着那个过程写。我写分解质因数时，脑子里始终记着一句话：找到一个质因子后，就把它从n里除掉，直到除不动为止。只要这句话没忘，循环条件、n的更新、最后的质数输出都能顺理成章地写对。

如果你现在正卡在东华OJ这道题上，建议按这个顺序排查：先跑n=1、n=4、n=质数这三组数据，再看输出里的等号和乘号，最后确认循环上界用的是不是n/i。这三关过了，这道题基本就稳了。