质因数、约数与最大公约数
本节目标
从质因数分解、成对约数到欧几里得算法，建立整除关系的基础工具链。
质数是乘法结构的原子：一个正整数可唯一拆成质因数幂的乘积。由这份分解可以理解约数的成对出现；而最大公约数则把两个数共同拥有的整除结构压缩进不断变小的余数。
识别信号
- 要写出一个整数的质因数及其指数，或统计其不同质因子；
- 要列出全部约数、统计约数个数，或处理因子对；
- 要消去两个整数的共同倍数关系，求最大公约数或约分。
核心定义与不变量
算术基本定理说明任意大于 1 的整数能唯一表示为 p₁^a₁ × p₂^a₂ × ...。若 d 是 n 的约数，n / d 也是约数，二者成对出现；完全平方数的平方根只形成一个约数，不能重复加入。
欧几里得算法维护 gcd(a, b) = gcd(b, a mod b)。任何同时整除 a、b 的数也整除余数，反过来任何同时整除 b、余数的数也整除 a，所以最大公约数不变。
朴素方法与瓶颈
分解或找约数时从 1 枚举到 n 显然正确，却会浪费对称的一半搜索。求最大公约数若从较小数向下试除，最坏情况接近线性；欧几里得算法每步用余数显著缩小第二个数。
推导与实现框架
对分解与约数枚举，都只需试到 divisor <= n / divisor。分解中每发现一个因子就持续除尽并记录指数；循环结束后的 n > 1 必是尚未记录的大质因子。约数枚举中同时加入 divisor 与 n / divisor，最后排序恢复递增结果。
求 GCD 时先取绝对值，再反复把 (a, b) 替换为 (b, a mod b)，直到 b = 0；此时 a 就是非负最大公约数，且自然处理一个参数为零的情况。
复杂度与数值边界
分解和约数枚举在单个 n 上均为 O(√n)；存储全部约数需要 O(τ(n)) 空间。欧几里得算法时间为 O(1 + log(max(|a|, |b|) + 1))、额外空间为 O(1)，这一写法也覆盖参数为零的情况。试除边界采用除法比较，不使用浮点 sqrt，同时避免精度与平方溢出风险。
母题序列
常见误区
- 分解后忘记加入循环结束时剩余的大质因子。
- 枚举约数时把完全平方数的平方根加入两次，或忘记排序。
- 使用
sqrt的浮点结果截断循环，漏掉平方根因子。 - GCD 没有统一符号，或错误地把
gcd(0, x)当成零。
迁移方向
质因数指数可推导欧拉函数、约数个数与整除计数；GCD 会在分数约分、模逆元、斜率规范化中反复出现。面对大量分解查询时，可将上一栏筛得的最小质因子表作为加速工具。