当一个数字决定“卸下伪装”：质因数分解的算法美学
先抛一个观点：质因数分解本质上是一次“身份还原”——每个合数都在伪装自己，用乘法把几个质数裹成一团，而我们要做的，就是把它一层层剥开，直到露出那些再也无法伪装的“素颜”。
这件事听起来简单，但它是数论的地基。RSA加密的安全性，就建立在“大整数质因数分解很难”这个事实上。也就是说，你手机里每一次安全支付，背后都站着一道关于质因数分解的计算壁垒。
拆积木的哲学
把一个合数拆成质数相乘，这件事的直觉非常朴素。12 = 2 × 2 × 3，30 = 2 × 3 × 5，没什么神秘的。但真正有意思的问题是：为什么试除到 √n 就可以停？
这个结论很多教材直接给出来，但我觉得它值得多想一步。假设 n 有一个大于 √n 的因子 p，那 n/p 一定小于 √n。也就是说，大因子总是和小因子成对出现。所以如果你从小到大试除数，一旦试过了 √n 还没找到任何因子，那说明 n 根本没有“小因子”——没有小因子就不可能有“大因子”，因为它们是成对的。
n 只能是自己。一个孤独的质数。
这个推理链条，是整个试除法的灵魂。代码里那句 i * i <= n 不是随便写的，它背后是“因子成对”这个数学事实。
代码的核心就三行
抛开输入检查和输出格式，质因数分解的算法骨架极其精简：
for (int i = 2; i * i <= n; i++) {
while (n % i == 0) {
factors.push_back(i);
n /= i;
}
}
if (n > 1) factors.push_back(n);
外层循环负责“换模具”，内层 while 负责“同一个模具反复压”——因为同一个质因子可能出现多次，比如 8 = 2 × 2 × 2，n 被 2 除了三次才变成 1。
而循环结束后那个 if (n > 1)，就是处理“最后剩下的孤独质数”的场景。比如分解 97，循环从 i=2 到 i=9（因为 9×9=81 < 97，但 10×10=100 > 97），一个因子都没找到，最后 n 还是 97，直接输出它自己。
循环条件 i * i <= n 里的 n 是动态变化的，这一点容易被忽略。每次 n /= i 之后，n 变小了，循环的上界也跟着收紧。比如分解 100，当 i=2 除完两次后 n=25，此时 i=3 时 9 ≤ 25 继续，i=4 时 16 ≤ 25 继续，i=5 时 25 ≤ 25 继续，除两次后 n=1，循环自然终止。这个动态收缩让算法比“固定试到 √原始n”要快不少。
题目里藏着的“变体”
来看一道题：已知 n 是两个不同质数的乘积，求较大的那个质数。
这道题表面上是质因数分解，但它有一个关键约束——n 只有两个质因子，且不相等。这意味着你不需要存因子数组，甚至不需要处理同一个质数出现多次的情况。从 i=2 开始试，第一个能整除 n 的 i 就是较小的质数，n/i 就是答案。
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
cout << n / i; // 直接输出较大的那个
return 0;
}
}
这道题的精妙之处在于：它逼你理解“两个质数相乘”意味着什么。因子成对出现，小的在 √n 以下，大的在 √n 以上。找到小的，大的自然浮出水面。
再看另一道题：素数分解——把一个正整数拆成互不相同的素数之和，问最多能拆成多少个。
注意，这里的“分解”和质因数分解完全是两回事。质因数分解是乘法拆解，这道题是加法拆分。但它们的底层思维有共通之处：都从最小的质数开始贪心。
为什么贪心是对的？因为要让素数个数最多，每个素数就应该尽可能小。从 2 开始，2+3+5+7+11 = 28，如果目标 n 大于这个和，就继续加下一个素数。但加到最后可能需要调整——如果剩余值恰好等于已用过的某个素数，就会违反“互不相同”的约束，需要把剩余值合并到最后一个素数上。
比如 21：2+3+5+7 = 17，还剩 4，但 4 不是素数，而且 4 也不能直接追加。正确做法是 2+3+5+11 = 21，把 7 和 4 合并成 11。这个调整过程才是这道题真正的难点。
一个容易踩的坑
很多人写试除法时会写成 i <= n 而不是 i * i <= n。对于小数字来说结果是对的，但效率差距巨大。分解 97，前者要循环 95 次，后者只要 8 次。
更隐蔽的坑是：i * i 可能溢出。如果 n 接近 INT_MAX，i * i 在 i 较大时会溢出成负数，导致循环条件永远为真。稳妥的写法是 i <= n / i，用除法代替乘法来避免溢出。
这些细节看起来琐碎，但它们区分了“能跑通的代码”和“能信任的代码”。
从分解到数论
质因数分解是很多数论算法的前置步骤。求最大公约数，取公共质因子的最小指数；求最小公倍数，取所有质因子的最大指数；判断完全平方数，看每个质因子的指数是否都是偶数。甚至求一个数的因数个数，也有公式：每个质因子的指数加一，然后全部相乘。
这些应用共享同一个底层认知：质因数分解给出了一个数的“原子结构”。一旦你知道了这个结构，很多关于这个数的问题就变成了对这个结构的简单操作。
而试除法，就是打开这个结构最直观的钥匙。它不花哨，不高效（对于大数来说远不如Pollard‘s Rho），但它的逻辑链条清晰到可以一步步推导出来——从最小的质数开始试，因子成对出现所以试到√n就够，剩下的如果大于1那它自己就是质数。
这种“每一步都有为什么”的算法，才是真正值得反复咀嚼的。
关于作者
我是赵老师，持有 NOI 信息学奥赛教练证书，拥有 15 年以上的软件开发经验，从事信息学少儿编程教学已有 8 年时间。
这些年累计帮助 多名 学生通过编程特长升入自己心仪的目标学校。
如果你在编程学习上有任何疑问，欢迎联系我：18620372957（微信同号）