写程序这些年我越来越觉得有一类问题特别值得用一整篇来聊聊它们单个拎出来都很简单但老是成组出现而且跟“数论入门”紧密挂钩。比如做分数计算器要约分分糖果和周期问题要凑公倍数因数和质因数更是刷题、笔试里的高频常客。用C实现质因数分解、最大公约数、最小公倍数、求所有因数本质上就是同一套数学思路下的四个出口代码之间还能相互复用。这篇文章我就把完整的实现、推导逻辑和踩过的坑从头到尾理一遍适合刚学完C语法、想在算法上落地练习的同学也适合准备笔试面试、想快速掌握数论工具箱的开发者。1. 四个问题其实是一家人数学关系与代码设计顺序很多人拿到这四个功能时会下意识把它们当成四个独立的小程序写一个丢一个。但如果你先花十分钟把它们的数学关系理清楚后面写代码会顺手得多因为每一步都在为下一步铺路。1.1 为什么质点分解要放在最前面质因数分解在整个体系里处于“地基”的位置一个整数一旦被拆成质因数的幂次乘积它包含哪些因数、有多少个因数、这些因数具体是什么都能很自然地推出来。最大公约数和最小公倍数虽然通常用辗转相除法去算不走分解路线但从质因数角度看它们其实也一目了然——取相同质因子的最小幂次就是最大公约数取最大幂次就是最小公倍数。所以我的建议是先实现一个可用的质因数分解函数把它当作后续多种能力的“母函数”。哪怕你已经决定最大公约数用经典欧几里得算法去写手上留一个分解函数也不亏它在求所有因数时会发挥关键作用这一点后面有专门章节展开。1.2 最大公约数和最小公倍数的推导关系最大公约数GCDGreatest Common Divisor和最小公倍数LCMLeast Common Multiple之间有一个很漂亮的公式如果d gcd(a, b)那么lcm(a, b) a * b / d。这个公式的直观理解是a * b的乘积里公共部分d被两个数各计了一次所以除掉一次d就是公倍数里最小的那个。从质因数分解的角度看假设 a 2^3 * 3^1b 2^1 * 3^2那么 gcd 是 2^1 * 3^1 6lcm 是 2^3 * 3^2 72而 a * b 432432 / 6 72完全对得上。这个公式的另一个意义是只要写好最大公约数最小公倍数就是一行代码的事不需要另起炉灶再搞一套算法。这也是为什么标题里四个功能要放在一起讲——它们的设计顺序是递进的不是并列的。1.3 从质因数到全体因数组合计数的思路假设 n p1^e1 * p2^e2 * ... * pk^ek那么 n 的每一个因数都长这样p1^c1 * p2^c2 * ... * pk^ck其中每个 ci 都在 0 到 ei 之间。换句话说每个质因子的指数都是“可选的档位”组合起来就是全部因数。这也顺便推导出了一个很有用的结论n 的因数个数等于 (e11) * (e21) * ... * (ek1)。比如 360 2^3 * 3^2 * 5^1因数个数是 (31) * (21) * (11) 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; vectorpairlong long, int factorizeNaive(long long n) { vectorpairlong 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第一次除完 2n 变成 3000009第二次除完 3n 直接变成 1000003后续循环只需试探到 1000 左右就结束了而不是傻乎乎地试到一千万。第三个优化是跳过偶数。2 是唯一的偶质数所以在处理完因子 2 之后d 可以从 3 开始每次加 2。更进阶一点可以按 6k±1 的形式递进跳过 2 和 3 的倍数不过原理是一样的。实际工程中跳过偶数带来的收益相当可观尤其是分解一个接近 10^12 的数字时循环次数直接减半。vectorpairlong long, int factorize(long long n) { vectorpairlong 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 内置版本与何时用哪种如果你用的编译器支持 C17标准库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 9000000000b 9000000000gcd 是 9000000000lcm 也是 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 36d 6需要专门去重。我推荐用两个容器分别存“小数因子”和“大数因子”最后把大数因子倒序接在小数因子后面省去排序天然有序#include vector using std::vector; vectorlong long getDivisorsByLoop(long long n) { vectorlong 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 vectorpairlong long, int factors, int idx, long long current, vectorlong 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; } } vectorlong long getDivisorsByFactorization(long long n) { auto factors factorize(n); vectorlong long res; dfsDivisors(factors, 0, 1, res); // 结果可以按需排序 return res; }这个方案的巧妙之处在于它把“求所有因数”从搜索问题变成了组合计数问题。对每个质因子你可以选 0 次、1 次、2 次……直到它在分解里的最高次数递归地往下枚举。最终 res 里装的就是全部因数数量正好等于之前提到的(e11)*(e21)*...*(ek1)。用 360 2^3 * 3^2 * 5^1 举例2 的指数可以取 0 到 33 的指数取 0 到 25 的指数取 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 vectorpairlong 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 vectorlong 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)应该等于 12lcm(360, 84)应该等于 2520getDivisors(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 先除后乘的顺序这些细节全部变成肌肉记忆之后再遇到相关问题就几乎不用想直接能写出正确的版本。这不是什么高深技巧就是最笨但最有效的学习路径。