1. 从一道面试题说起为什么分解质因数这么重要前几天帮一个学弟复盘面试他挂在了二面的一道基础算法题上。题目很简单给定一个正整数 N请输出它的所有质因数及其对应的指数。比如输入 12输出2^2 * 3^1。学弟当时用了最朴素的思路——从 2 遍历到 N判断每个数是否能整除 N如果是质数就记录。结果当 N 接近 10^9 时程序直接超时。面试官追问优化思路他卡壳了。这其实暴露了一个很典型的问题很多初学者对“分解质因数”的理解还停留在小学数学的概念层面没有将其转化为高效的算法思维。而在算法竞赛如 AcWing、LeetCode和实际开发如 RSA 加密原理、哈希冲突处理中质因数分解是理解数论、设计高效算法的基石。AcWing 算法基础课将其作为数论部分的核心内容正是因为它承上启下是理解后续欧拉函数、约数个数等知识的关键。试除法作为分解质因数最直观、最基础的算法其价值不在于处理极大的数字那是 Pollard Rho 算法的领域而在于它完美地体现了“用计算机思维解决数学问题”的过程。通过它我们能深刻理解时间复杂度分析、循环边界优化、以及如何利用数学性质如“一个合数必有一个不大于其平方根的质因数”来大幅提升效率。今天我们就抛开教科书的刻板描述从实战和原理出发把试除法分解质因数这件事掰开揉碎了讲清楚。2. 试除法的核心原理不只是“除”那么简单试除法的思想非常直接对于一个正整数n我们从小到大枚举所有可能的质因数i如果能整除就不断地除以i直到不能整除为止同时记录除的次数即指数。枚举完如果n还大于 1那么剩下的n本身就是一个质数。这个描述听起来平平无奇但其中蕴含了两个至关重要的优化点也是面试和笔试中区分“背答案”和“真理解”的关键。2.1 优化一枚举到 sqrt(n) 就够了吗这是最广为人知的优化。原理是如果n是一个合数那么它必定有一个不大于sqrt(n)的质因子。这个结论是试除法效率的基石。为什么我们可以用反证法来理解。假设n的所有质因子都大于sqrt(n)。设最小的质因子为p那么p sqrt(n)。因为n是合数至少还有一个因子q n / p。由于p是最小的所以q p sqrt(n)。那么p * q sqrt(n) * sqrt(n) n这与p * q n矛盾。因此假设不成立n必有一个不大于sqrt(n)的质因子。在代码中这意味着我们的for循环条件可以写成i n / i等价于i * i n但能防止i*i溢出。这个小小的改动能将时间复杂度从 O(n) 降为 O(sqrt(n))对于n10^9的情况遍历次数从十亿级降到了三万级这是质的飞跃。注意这里有一个新手极易混淆的点。循环条件是i n / i但循环体内的n是动态变化的每次除尽质因子后n会变小。这个条件依然正确吗正确。因为当我们枚举到i时n中所有小于i的质因子都已经被除干净了。如果当前i能整除n那么i必然是质数证明如果i是合数那么它的质因子小于i而这些小于i的质因子已经在之前被枚举并除尽了矛盾。因此我们始终在枚举质因子而n的剩余部分其最小质因子一定大于等于当前的i。所以当i大于sqrt(当前n)时当前n要么是 1要么是一个质数。循环结束后对n 1的处理正是为了收集这个最后的质因子。2.2 优化二为什么可以放心地每次i这是第二个精妙之处。我们并没有在循环里判断i是否为质数而是直接判断n % i 0。如果i是合数它可能整除n吗答案是不可能。原因接续上面的逻辑当代码执行到i时n中所有小于i的质因子已经被除尽。如果i是合数设其某个质因子为pp i。因为p是i的因子如果i能整除n那么p也一定能整除n。但这与“n中所有小于i的质因子已被除尽”矛盾因为p小于i且是质数。因此凡是能进入if (n % i 0)分支的i一定是质数。这个特性省去了每次判断i是否为质数的开销让代码极其简洁高效。它依赖于算法步骤本身带来的“过滤”效果是理解试除法逻辑闭环的关键。3. 手把手实现代码逐行解析与避坑指南理解了原理我们来看 C 的标准实现。我会逐行分析并指出几个常见的“坑”。void divide(int n) { // 遍历所有可能的小于等于sqrt(n)的质因子 for (int i 2; i n / i; i) { // 如果i能整除n那么i一定是n的质因子 if (n % i 0) { int s 0; // 指数计数器 // 将n中所有因子i除尽 while (n % i 0) { n / i; s; } // 输出质因子i及其指数s printf(%d %d\n, i, s); } } // 处理可能剩余的那个大于sqrt(原始n)的质因子 if (n 1) { printf(%d %d\n, n, 1); } }逐行解读与避坑点循环条件i n / i这是防止整数溢出的最佳写法。写成i * i n在i较大时可能导致i*i溢出。写成i sqrt(n)则需要每次循环计算sqrt有精度和性能开销。i n / i是最优选择。if (n % i 0)的判断如前所述走到这里的i一定是质数。这是算法的“魔法”所在无需额外判断。while (n % i 0)循环这个循环有两个作用。一是精确计算质因子i的指数s二是在计算过程中不断减小n这直接影响了外层for循环的终止条件i n / i使得算法能提前结束。这是动态边界带来的额外效率提升。最后的if (n 1)这是整个算法的收尾关键也是最容易被遗忘的一步。经过循环后n的值可能变为 1说明所有质因子都已找到也可能是一个大于 1 的数。根据优化一的原理这个大于 1 的n一定是原始n的一个质因子并且它大于原始n的平方根。例如n 13质数循环不会进入因为2 13/2最后n13 1输出13 1。再如n 22循环会找到质因子 2除尽后n变为 11此时i33 11/3循环结束剩余的n11就是另一个质因子。一个经典的调试案例假设输入n 12。i2满足2 12/2进入循环。12 % 2 0成立进入内层whilen依次变为 6, 3s2。输出2 2。i3此时n3满足3 3/3即3 1不成立。注意这里循环条件i n / i变成了3 3/3 1为假所以外层for循环结束。执行最后的if (n 1)此时n3输出3 1。 结果正确12 2^2 * 3^1。这个例子清晰地展示了动态n如何使循环提前终止。4. 时间复杂度分析与不同场景下的表现我们常说试除法分解质因数的时间复杂度是 O(sqrt(n))。这个说法需要细化因为它描述的是最坏情况。最坏情况当n本身是一个质数时我们需要遍历i从 2 到sqrt(n)才能确认时间复杂度为 O(sqrt(n))。最好情况当n是 2 的幂如n2^k时第一次循环i2就会进入while将n除到 1循环提前结束时间复杂度接近 O(log n)。平均情况复杂度低于 O(sqrt(n))因为n会在除尽小因子后迅速变小缩短了循环次数。但对于算法分析我们通常用最坏复杂度来评估其性能上限。在实际应用和算法题中这个复杂度意味着对于n 10^7的情况试除法游刃有余。对于n 10^9的情况sqrt(10^9) ≈ 31622三万多次循环在现代计算机上也是瞬间完成完全可行。对于n 10^12或更大试除法就会开始吃力百万次循环这时就需要更高级的算法如 Pollard Rho时间复杂度期望为 O(n^{1/4})。这里分享一个我踩过的坑在一次线上比赛中题目需要对多个数进行质因数分解我直接对每个数调用divide函数。当查询次数Q很大如Q10^5且每个数n都接近10^9时总计算量Q * sqrt(n)就会超时。正确的优化思路是预处理先用线性筛法求出一定范围内如sqrt(最大n)的所有质数存储在数组中。然后在divide函数中不再用i枚举所有数而是直接枚举预处理好的质数数组。这样内层循环次数从sqrt(n)降为了sqrt(n) / log(sqrt(n))对于大量查询的场景性能提升显著。5. 不止于分解质因数分解的典型应用场景理解了算法更要明白用它来做什么。质因数分解绝不是一道孤立的算法题它是解决许多复杂问题的“瑞士军刀”。5.1 计算正整数的约数个数与约数之和这是最直接的应用。根据数论定理如果一个数N质因数分解为N p1^a1 * p2^a2 * ... * pk^ak。那么它的约数个数为(a11) * (a21) * ... * (ak1)。每个质因子可以取 0 到 ai 次幂相乘得到所有组合它的约数之和为(p1^0 p1^1 ... p1^a1) * ... * (pk^0 ... pk^ak)。利用试除法得到pi和ai后这两个值可以轻松算出。很多题目会伪装成“求约数个数”本质就是考质因数分解。5.2 判断两个数是否互质如果两个数a和b的最大公约数gcd(a, b) 1则它们互质。一种方法是用欧几里得算法求gcd。另一种思路是分别分解a和b的质因数如果它们没有公共的质因子则互质。虽然效率不如gcd但这种思路在需要同时获取质因数信息的场景下很有用。5.3 简化分数或比例问题例如题目要求将分数a/b化为最简形式。我们需要找到分子分母的最大公约数g然后同时除以g。如何找g可以对a和b分别分解质因数找出所有公共质因子的最低次幂乘积就是g。这同样是欧几里得算法的替代思路在某些特定场景下如需要记录化简过程更直观。5.4 解决模运算与同余方程在初等数论中解一些同余方程时常常需要将模数m分解质因数然后转化为若干个模p^kp是质数的方程再用中国剩余定理组合解。这是 RSA 等加密算法背后的数学原理之一。实战心得不要死记硬背应用场景。最好的方法是每当你看到一个算法都问自己“这个算法的输出结果质因数列表能用来计算什么” 把质因数分解看作一个信息提取工具它把整数n压缩成了一组(质数, 指数)的键值对。后续几乎所有关于n的算术性质问题都可以通过操作这组键值对来高效解决。这种“降维”思维才是学习算法的核心。6. 从试除法出发算法思想的延伸与对比试除法是“暴力枚举”思想在数论领域的经典体现。通过它我们可以延伸到其他重要的算法思想。与判断质数的试除法对比判断单个数n是否为质数也可以用类似的循环for (int i2; in/i; i)。但注意那里没有内层的while循环因为目的只是判断是否存在一个因子找到任何一个就可以立即返回false。而分解质因数要求找出所有因子所以需要while除尽。两者代码相似但目的和细节的差异恰恰是面试官喜欢考察的点。向更高效算法的演进当n很大时试除法O(sqrt(n))的复杂度不够用。于是有了Miller-Rabin 素性测试一个基于概率的快速判断大数是否为质数的算法。Pollard Rho 因数分解算法一个用于分解大整数的随机算法期望时间复杂度为O(n^{1/4})。它的核心思想之一是“随机漫步”和“生日悖论”与试除法的确定性枚举截然不同。学习试除法是理解这些高级算法为何必要、以及它们优化了什么的基石。在 AcWing 课程体系中的位置在 AcWing 算法基础课的数论章节试除法分解质因数通常紧接在“试除法判断质数”之后位于“筛质数”埃氏筛、线性筛之前。这个安排非常合理它先用小规模问题单个数引入枚举和优化思想然后过渡到需要获取完整质因数信息的“分解”问题最后再推广到需要一次性处理大量数的“筛选”问题。层层递进由点及面。我个人的学习建议是在学完试除法后一定要手动模拟分解几个典型数字比如 24, 56, 97, 1001。在纸上一步步走完循环观察n和i的变化。这个过程能极大地强化你对“动态边界”和“最后剩余质因子”这两个关键点的理解。很多逻辑上的疑惑在纸笔模拟面前都会烟消云散。最后虽然现在有很多模板代码可以直接套用但我强烈建议在初学阶段自己从头实现几遍。从最朴素的O(n)版本开始逐步加入sqrt(n)优化最后写出带n1处理的完整版。这个迭代过程能让你真正内化算法的每一个优化步骤明白其所以然。当你再遇到类似“枚举优化”的问题时这种思维模式会自然而然地浮现出来这才是刷算法题最重要的收获。