写程序这些年，我越来越觉得有一类问题特别值得用一整篇来聊聊：它们单个拎出来都很简单，但老是成组出现，而且跟“数论入门”紧密挂钩。比如做分数计算器要约分，分糖果和周期问题要凑公倍数，因数和质因数更是刷题、笔试里的高频常客。用C++实现质因数分解、最大公约数、最小公倍数、求所有因数，本质上就是同一套数学思路下的四个出口，代码之间还能相互复用。这篇文章我就把完整的实现、推导逻辑和踩过的坑从头到尾理一遍，适合刚学完C++语法、想在算法上落地练习的同学，也适合准备笔试面试、想快速掌握数论工具箱的开发者。
1. 四个问题其实是一家人：数学关系与代码设计顺序
很多人拿到这四个功能时，会下意识把它们当成四个独立的小程序，写一个丢一个。但如果你先花十分钟把它们的数学关系理清楚，后面写代码会顺手得多，因为每一步都在为下一步铺路。
1.1 为什么质点分解要放在最前面
质因数分解在整个体系里处于“地基”的位置：一个整数一旦被拆成质因数的幂次乘积，它包含哪些因数、有多少个因数、这些因数具体是什么，都能很自然地推出来。最大公约数和最小公倍数虽然通常用辗转相除法去算，不走分解路线，但从质因数角度看它们其实也一目了然——取相同质因子的最小幂次就是最大公约数，取最大幂次就是最小公倍数。
所以我的建议是：先实现一个可用的质因数分解函数，把它当作后续多种能力的“母函数”。哪怕你已经决定最大公约数用经典欧几里得算法去写，手上留一个分解函数也不亏，它在求所有因数时会发挥关键作用，这一点后面有专门章节展开。
1.2 最大公约数和最小公倍数的推导关系
最大公约数（GCD，Greatest Common Divisor）和最小公倍数（LCM，Least Common Multiple）之间有一个很漂亮的公式：
如果d = gcd(a, b)，那么lcm(a, b) = a * b / d。
这个公式的直观理解是：a * b的乘积里，公共部分d被两个数各计了一次，所以除掉一次d就是公倍数里最小的那个。从质因数分解的角度看，假设 a = 2^3 * 3^1，b = 2^1 * 3^2，那么 gcd 是 2^1 * 3^1 = 6，lcm 是 2^3 * 3^2 = 72，而 a * b = 432，432 / 6 = 72，完全对得上。
这个公式的另一个意义是：只要写好最大公约数，最小公倍数就是一行代码的事，不需要另起炉灶再搞一套算法。这也是为什么标题里四个功能要放在一起讲——它们的设计顺序是递进的，不是并列的。
1.3 从质因数到全体因数：组合计数的思路
假设 n = p1^e1 * p2^e2 * ... * pk^ek，那么 n 的每一个因数都长这样：p1^c1 * p2^c2 * ... * pk^ck，其中每个 ci 都在 0 到 ei 之间。换句话说，每个质因子的指数都是“可选的档位”，组合起来就是全部因数。
这也顺便推导出了一个很有用的结论：n 的因数个数等于 (e1+1) * (e2+1) * ... * (ek+1)。比如 360 = 2^3 * 3^2 * 5^1，因数个数是 (3+1) * (2+1) * (1+1) = 24 个。写“求所有因数”的代码时，如果直接用暴力枚举从 1 试到 n，数据一大就跑不动；而基于分解结果的组合生成方案，在结构上更优雅，也更能体现这四个功能之间的协同关系。
为了方便后面对照，把四个功能的目标和常规复杂度先列出来：
| 功能 | 推荐核心算法 | 时间复杂度 | 典型应用场景 |
|---|---|---|---|
| 质因数分解 | 改进试除法 | O(sqrt(n)) | 数论题前置步骤、求因数个数 |
| 最大公约数 | 辗转相除法 | O(log(min(a, b))) | 约分、分数运算、线性同余 |
| 最小公倍数 | 基于 GCD 公式 | O(log(min(a, b))) | 周期同步、分糖问题 |
| 求所有因数 | 对称枚举或分解组合 | O(sqrt(n)) / O(因数个数) | 因数求和、完全数判断 |
2. 质因数分解：从最朴素的试除法到可用版本
质因数分解的算法有很多，从简单的试除法到 Pollard-Rho 再到二次筛法，难度跨度非常大。但对于绝大多数日常需求，改进试除法已经足够。这个章节里我带你走一遍完整的思路转变过程，不直接甩最终代码。
2.1 先写出能跑的版本：2 到 n 的遍历
最原始的版本几乎不用动脑筋：从 2 开始，只要 n 能被 d 整除，就一直除，同时统计次数；d 每次加 1，直到 d 超过 n 本身。
#include <vector> using std::vector; using std::pair; vector<pair<long long, int>> factorizeNaive(long long n) { vector<pair<long long, int>> res; for (long long d = 2; d <= n; ++d) { if (n % d == 0) { int cnt = 0; while (n % d == 0) { n /= d; ++cnt; } res.push_back({d, cnt}); } } return res; }这个版本对 n = 100 这种小数字毫无压力，但一旦 n 是十亿级别，循环上限直接飙到十亿，慢得让人怀疑人生。问题出在哪？我们把大量时间浪费在“d 不是 n 的因子却依然要一次次判断”上，而且根本没有意识到 n 在分解过程中会越变越小。
2.2 三个关键优化：只试到 sqrt(n)、提前除尽、跳过偶数
第一个优化是循环上限改成d * d <= n。这里有个数学事实：如果 n 是合数，它一定有一个质因子不超过 sqrt(n)。所以试到 sqrt(n) 就够了，如果循环结束了 n 还大于 1，那剩下的 n 本身就是最后一个质因子。这个性质的另一个好处是：大于 sqrt(n) 的质因子最多只有一个，因为两个大于 sqrt(n) 的数相乘一定大于 n，这就让收尾变得很干净。
第二个优化藏在 while 循环里：每找到一个因子就立刻把 n 连除到干净。这不仅是记录幂次的需要，更是让 n 快速缩小的关键。比如 n = 2 * 3 * 1000003，第一次除完 2，n 变成 3000009，第二次除完 3，n 直接变成 1000003，后续循环只需试探到 1000 左右就结束了，而不是傻乎乎地试到一千万。
第三个优化是跳过偶数。2 是唯一的偶质数，所以在处理完因子 2 之后，d 可以从 3 开始，每次加 2。更进阶一点可以按 6k±1 的形式递进，跳过 2 和 3 的倍数，不过原理是一样的。实际工程中，跳过偶数带来的收益相当可观，尤其是分解一个接近 10^12 的数字时，循环次数直接减半。
vector<pair<long long, int>> factorize(long long n) { vector<pair<long long, int>> res; for (long long d = 2; d <= n / d; ++d) { if (d > 2 && d % 2 == 0) continue; // 更常用的是先处理 2，然后 d += 2 if (n % d == 0) { int cnt = 0; while (n % d == 0) { n /= d; ++cnt; } res.push_back({d, cnt}); } } if (n > 1) res.push_back({n, 1}); return res; }我把循环条件写成了d <= n / d，而不是d * d <= n。原因很简单：d * d在 n 接近 long long 上限时可能溢出，而n / d是除法运算，没有任何风险。这算是一个面对大数时必须养成的条件反射。
2.3 边界情况与复杂度分析
边界情况主要就三类：n = 1、n 是质数、n 是完全平方数。
n = 1 时没有任何质因子，直接返回空结果，调用方要自己决定怎么解释这个空向量。n 是质数时，外层循环什么都试不出来，最后靠if (n > 1)把它自己收进结果。n = 49 这样的完全平方数，最后 n 会被除成 1，不会有多余的尾项，所以n > 1这个判断天然帮你避免了重复记 7 的情况。
从复杂度上讲，改进试除法是 O(sqrt(n)) 的。但很多人没注意到一个细节：这里的 sqrt(n) 是“动态”的，因为 n 在每找到一个因子后都会变小，实际循环次数往往远小于 sqrt(原始 n)。比如分解 2 * 999983，初始循环上限大约是 1414，除完 2 之后 n 变成 999983，上限立刻下降到 999 左右，整体非常快。
我测试过一个 10^12 量级、由两个大质数相乘得到的数，改进试除法在普通机器上大概跑了几秒，而朴素版基本等不到结果。这已经足以说明问题：不需要急着上高级算法，先把试除法优化到极限，大部分场景都够用。
3. 最大公约数：为什么辗转相除法值得信任
最大公约数可能是这四个功能里“最不需要解释原理、但最容易写错细节”的一个。因为很多同学背得住gcd(a, b) = gcd(b, a % b)这个公式，却不清楚它为什么成立，一旦遇到递归写法、迭代写法、负数输入、大数输入这些变体，就会开始出问题。
3.1 暴力枚举与更相减损术的短板
先看暴力枚举：从min(a, b)开始往下找，找到第一个能同时整除 a 和 b 的数就是答案。代码简单到不行：
long long gcdByEnum(long long a, long long b) { long long limit = (a < b) ? a : b; for (long long d = limit; d >= 1; --d) { if (a % d == 0 && b % d == 0) return d; } return 1; }问题是：如果 a 和 b 都是 10^9 量级且互质，这个循环要跑十亿次，等得花儿都谢了。它唯一的优点是完全符合直觉，适合教学演示，不适合任何实际场景。
更相减损术是古老的中国算法思路：gcd(a, b) = gcd(b, a-b)，不断用大数减小数，直到两数相等。它正确，但最坏情况下退化成“一个数减一”的形式，比如 gcd(1, 1000000007)，要做一亿次减法。虽然可以优化成“一次减多个”，但那已经是半只脚踏进辗转相除法的思路了。
3.2 欧几里得算法的原理与三种写法
欧几里得算法（辗转相除法）的核心是取模而非减法，这让它的收敛速度快得多。原理其实一句话就能讲清楚：若 a = q * b + r，则任何能同时整除 a 和 b 的数，也一定能整除 r = a - q * b；反过来，任何能同时整除 b 和 r 的数，也一定能整除 a。所以 gcd(a, b) = gcd(b, r)，也就是 gcd(a, b) = gcd(b, a % b)。
这个等式在 b = 0 时自然结束，因为 gcd(x, 0) = x。
递归写法最贴近数学定义，看代码就能想起来公式：
long long gcdRecursive(long long a, long long b) { return b == 0 ? a : gcdRecursive(b, a % b); }迭代写法避免了递归栈深度的问题，也是我现在最常用的版本：
long long gcdIterative(long long a, long long b) { while (b != 0) { long long tmp = a % b; a = b; b = tmp; } return a; }两种写法的时间复杂度都是 O(log(min(a, b)))。为什么这么快？因为每次取模后，较大的数至少缩水到原来的一半以内，最坏情况下迭代次数也是常数级别的几十次，几乎可以忽略。我用自己的机器实测过递归版本，十几亿级别的两个数，耗时在微秒级别，暴力枚举完全没法比。
3.3 内置版本与何时用哪种
如果你用的编译器支持 C++17，标准库<numeric>里已经提供了std::gcd，可以直接用：
#include <numeric> long long g = std::gcd(360LL, 84LL);标准库版本内部经过了充分测试，还处理了各种类型细节。我自己的原则是这样的：日常写项目、刷题时直接用std::gcd，省心又不容易错；但学习阶段一定得亲手写一遍递归版和迭代版，因为笔试环境不一定允许你依赖标准库版本，而且手写版本能帮你真正理解算法而不是背 API。
顺便提一下，欧几里得算法对负数的处理在不同语言里略有差异。C++ 的%运算结果是负数时，不会影响 gcd 的最终结果，因为 gcd 定义里取绝对值即可。你可以在函数入口对 a、b 各自取绝对值，但要注意 long long 的最小值取绝对值会溢出，这个细节极其隐蔽，实际做题时如果数据范围卡得很死，建议直接用std::gcd或使用 unsigned long long 参与运算。
4. 最小公倍数：先除后乘是必修课
最小公倍数是这四个功能里最短的一段代码，但也是我见过最容易因为“想当然”而写错的。问题核心在于溢出，也在于很多人背熟了公式却不理解括号为什么要那样放。
4.1 公式推导与溢出问题
基于前面讲的公式，最小公倍数的常见写法有两种：
// 先乘后除：可能溢出 long long lcmBad(long long a, long long b) { return a * b / gcd(a, b); } // 先除后乘：推荐 long long lcmGood(long long a, long long b) { return a / gcd(a, b) * b; }两种写法数学上等价的，但实际效果天差地别。假设 a = 9000000000，b = 9000000000，gcd 是 9000000000，lcm 也是 9000000000。先乘后除时，a * b已经达到 8.1 * 10^19，远超 long long 的约 9.2 * 10^18 上限，直接溢出成负数；先除后乘则是 1 * 9000000000，完全安全。
这个道理就像是先约分再相乘：a / gcd(a, b)已经把 a 里跟 b 重复的部分去掉了，剩下的乘积天然就是不超过 a * b 的“最小公倍数”，所以在数据范围内几乎不可能溢出（除非真实结果本身就超出 long long 范围）。
4.2 实现细节与多个数推广
如果求三个数或多个数的最小公倍数，只需要分步计算：
long long lcm(long long a, long long b) { return a / gcdIterative(a, b) * b; } long long lcmThree(long long a, long long b, long long c) { return lcm(lcm(a, b), c); }这里有个细节值得注意：两个数的最小公倍数再跟第三个数求最小公倍数，顺序不会影响最终结果，但中间结果可能暂时超过最终值。比如 lcm(6, 10) = 30，再用 30 跟 14 求 lcm，得到 210，中间值 30 没有超过 210，安全；但某些组合里中间值可能比最终结果大，比如 lcm(13, 17) = 221，再跟 19 求 lcm，中间值 221 小于最终 4199，而反向顺序 lcm(17, 19) = 323，再跟 13 求 lcm，中间值 323 也小于最终 4199，看起来没问题。可总有组合会让中间值略大于最终值，所以稳妥起见，三个数运算时也要关注中间值的溢出风险。如果数字很大，建议一边算一边用__int128做中转，这里不展开，但要记住这个隐患。
我自己踩过的坑是：写分数类的时候，对分母求完 lcm 后直接拿 long long 去接，结果在分母是数千万量级时莫名其妙出现负数，排查半天才发现是中间过程的a * b溢出，改成先除后乘后立刻恢复。这种错误特别隐蔽，因为它只在特定数据范围内才炸，习惯性写a * b / gcd的人很容易中招。
5. 求所有因数：两条路线各有各的舒服区
求所有因数是个看似不起眼、代码却能写得千奇百怪的功能。核心问题是如何不重复、不遗漏地枚举全部因数，同时保证性能能扛住大数。两条主路线分别对应不同的思维习惯，我在这里都展开讲。
5.1 路线一：对称枚举到 sqrt(n)
最基本的数学观察是：如果一个数 d 是 n 的因数，那么 n / d 也一定是 n 的因数。d 和 n / d 成对出现，并且总有一方不超过 sqrt(n)。所以只需要枚举 d 从 1 到 sqrt(n)，然后对称地把 n / d 也放进结果。
如果不加处理，直接用一个向量边找边 push，结果会是无序的，而且一个 d 和 n / d 可能相等（当 d * d == n 时，比如 n = 36，d = 6），需要专门去重。我推荐用两个容器分别存“小数因子”和“大数因子”，最后把大数因子倒序接在小数因子后面，省去排序，天然有序：
#include <vector> using std::vector; vector<long long> getDivisorsByLoop(long long n) { vector<long long> small, big; for (long long d = 1; d <= n / d; ++d) { if (n % d == 0) { small.push_back(d); if (d != n / d) { big.push_back(n / d); } } } for (auto it = big.rbegin(); it != big.rend(); ++it) { small.push_back(*it); } return small; }这段代码的边界处理值得细品：d != n / d的判断直接处理了完全平方数的中心因子重复问题；大数因子倒序接入，保证整个结果是升序的。复杂度是 O(sqrt(n))，而且真正的循环次数只有 sqrt(n) 次，非常稳定，适合绝大多数的日常场景。
我自己常用这个函数测试一个数是否是完全数（所有真因数之和等于自身），配合因数列表，整个过程只需要几行代码。
5.2 路线二：基于质因数分解的组合生成
如果你手里已经有了第 2 章的factorize函数，那么求所有因数可以有另一条更符合“数论本色”的路线：先分解，再对每个质因子的指数做组合枚举。
#include <vector> using std::vector; using std::pair; void dfsDivisors( const vector<pair<long long, int>>& factors, int idx, long long current, vector<long long>& out ) { if (idx == (int)factors.size()) { out.push_back(current); return; } long long p = factors[idx].first; int e = factors[idx].second; long long power = 1; for (int i = 0; i <= e; ++i) { dfsDivisors(factors, idx + 1, current * power, out); power *= p; } } vector<long long> getDivisorsByFactorization(long long n) { auto factors = factorize(n); vector<long long> res; dfsDivisors(factors, 0, 1, res); // 结果可以按需排序 return res; }这个方案的巧妙之处在于：它把“求所有因数”从搜索问题变成了组合计数问题。对每个质因子，你可以选 0 次、1 次、2 次……直到它在分解里的最高次数，递归地往下枚举。最终 res 里装的就是全部因数，数量正好等于之前提到的(e1+1)*(e2+1)*...*(ek+1)。
用 360 = 2^3 * 3^2 * 5^1 举例：2 的指数可以取 0 到 3，3 的指数取 0 到 2，5 的指数取 0 到 1，组合起来一共 4 * 3 * 2 = 24 个因数，包括 1、2、4、8、3、6、12、24、9、18、36、72、5、10、20、40、15、30、60、120、45、90、180、360。递归顺序下结果不保证升序，所以如果对顺序有要求，需要调用sort，这是它与路线一相比唯一的劣势。
5.3 复杂度对比与选型建议
路线一的枚举次数严格等于 sqrt(n)，与 n 的因数个数无关。路线二的耗时分成两块：分解部分 O(sqrt(n))，组合生成部分 O(因数个数)。对于因数很多的“超合数”，比如 73513440 这种，路线二的生成部分本身就有大量输出，跑得再快也得把结果写出来，差异不大；但对于 n 是质数的情况，路线一只用循环 sqrt(n) 次就能确认答案，路线二先分解（也要循环 sqrt(n) 次）再生成（只有 2 个因数），整体也差不多。
我的选型建议很直接：如果只需要求一次因数，用路线一，代码短、逻辑容易验证、天然有序；如果你本来就要对同一批数做质因数分解（比如批量统计因数个数），直接用路线二，因为它跟分解函数配合起来思路非常清晰，还能顺便复用结果做其他推断。一个真实的例子是我写“欧拉函数 φ(n)”相关代码时，先分解再组合的路子让它变得特别直观，因为欧拉函数本身就是基于质因子计算的。
6. 封装成工具类后的真实体验与调试心得
把这四个功能全部写完，自然就会想封装成一个工具类，方便复用。最终的完整代码其实很紧凑，但由于篇幅原因这里给出类的声明和几个关键函数的实现思路，你可以直接照抄组合。
6.1 一个简单的 NumberTheory 工具类
class NumberTheory { public: // 质因数分解，返回 {质因子, 幂次} 向量 static vector<pair<long long, int>> factorize(long long n); // 最大公约数（辗转相除法） static long long gcd(long long a, long long b); // 最小公倍数（基于 gcd） static long long lcm(long long a, long long b); // 求全部因数（基于质因数分解） static vector<long long> getDivisors(long long n); // 因数个数（基于分解结果，不生成具体因数） static long long countDivisors(long long n); };这个类设计成静态方法就很合适，因为每个方法都是纯函数，不依赖任何成员变量。countDivisors是最容易顺手加上的一个功能：既然已经拿到分解向量，只需要对每个幂次加一再乘起来，一行循环的事，不需要真的展开所有因数。
示例调用：
long long n = 360; auto factors = NumberTheory::factorize(n); auto divs = NumberTheory::getDivisors(n); long long cnt = NumberTheory::countDivisors(n); // cnt = 24这里有一点封装上的经验：不要把分解结果的顺序作为公共接口的承诺。不同实现可能返回升序、可能按发现顺序，调用方如果依赖顺序，容易在某个版本更新后悄悄出错。如果确实需要有序输出，在工具类内部做好排序更稳妥。
6.2 大数边界与性能观察
我用一组数字做了简单测试，覆盖从 100 到 1999999999 的范围，循环枚举因数和分解基本上都在毫秒以内。但 n 一旦超过 10^12，试除法就开始吃力了，因为 sqrt(n) 大约是 10^6，百万级别的循环在纯 C++ 下还能忍；到了 10^14 以上，sqrt(n) 变成千万级别，单次调用就会有几秒延迟。这时候要考虑进阶方案，比如用轮子法减少模运算次数，或者直接把输入限制在适合试除法的范围。
对求因数功能本身，还有一个容易被忽略的性能问题：结果的存储顺序和内存分配。如果 n 的因数特别多（比如 100 万级别），用 vector 反复 push_back 会触发多次扩容，建议一次性reserve到大概countDivisors的数量。这个优化虽然用不上因数个数公式，但在处理大型合数时收益很明显。
6.3 我的调试经验和几个容易忽略的细节
调试这类数学函数，最好用的方法就是拿已知结论反推：比如用gcd(360, 84)应该等于 12，lcm(360, 84)应该等于 2520，getDivisors(36)应该是 1、2、3、4、6、9、12、18、36。把这些固定用例做成断言，每次改动后跑一遍，比肉眼检查可靠得多。
几个容易出问题的小地方：
d <= n / d而不是d * d <= n，这个前面强调过，是面对大数的安全习惯。
质因数分解循环里的 d 不需要每次加 1，处理完因子 2 后可以直接从 3 开始步进 2。但要注意一个不算坑的坑：d 本身必须是整数，如果你写for (long long d = 3; d <= n / d; d += 2)，循环退出时最后还要判断 n 是否大于 1，这个逻辑是安全的，但一定要写在循环外面，别漏掉最后一个大于 sqrt(原始 n) 的质因子。
求所有因数的路线一里，d != n / d的判断很关键，少了它完全平方数会把中心因数重复计算一次。我在早期版本里就没写这个判断，测试 36 时得到了一串带重复 6 的结果，后来加了断言才发现。
最后提一个方法论层面的心得：这四个功能虽然简单，但它们是你理解更高级数论算法的“基准训练”。我在后来接触 Pollard-Rho 分解、莫比乌斯反演、欧拉函数扩展时，早期亲手写过这几段基础代码的底子起了很大作用。比如 Pollard-Rho 的核心就是不断找非平凡因子，而找因子的基础思路跟这里求最小因数几乎同源；欧拉函数公式里那个(1 - 1/p)的拆分，也要先习惯从质因数分解开始思考。
如果有时间，建议把这几段代码从头到尾手敲一遍，不要复制粘贴。我自己的体验是：敲一遍和看一遍的差距，比想象中大得多。质因数分解的循环跳法、gcd 递归的终止条件、lcm 先除后乘的顺序，这些细节全部变成肌肉记忆之后，再遇到相关问题就几乎不用想，直接能写出正确的版本。这不是什么高深技巧，就是最笨但最有效的学习路径。
与SE(3)位姿表示及优化实战指南)
