工作原理
最大公约数(GCD)用欧几里得算法(辗转相除法)计算:用较大数除以较小数的余数替换较大数,直到余数为 0。三个及以上的数则两两依次计算。
最小公倍数(LCM)由最大公约数得出:lcm(a, b) = |a × b| ÷ gcd(a, b),同样两两计算。全部使用精确整数运算,30 位的数也没有误差。
辗转相除法分步演示
以 1071 和 462 为例:每一行用上一行的除数除以余数,最后一个非零余数就是最大公约数。
- 1071 = 2 × 462 + 147
- 462 = 3 × 147 + 21
- 147 = 7 × 21 + 0 → gcd = 21
gcd(a, b) = gcd(b, a mod b) · lcm(a, b) = |a × b| ÷ gcd(a, b)
用在哪里
- 最大公约数:约分,例如 18/24 除以最大公约数 6 得 3/4。
- 最小公倍数:通分,或计算周期不同的事件何时再次重合(每 4 天和每 6 天 → 每 12 天)。
- 最大公约数:把瓷砖、行或小组无剩余地分成同样大小。
提示
- 最大公约数为 1 时两数互质;像 8 和 9 这样都是合数也可以互质。
- 对两个正整数,gcd(a, b) × lcm(a, b) = a × b,可用来验算。
- 可以输入 0:gcd(a, 0) = a,但含 0 的最小公倍数是 0。
标准与出处
最后核对于 2026年10月20日
常见问题
最大公约数和最小公倍数有什么区别?
最大公约数是能整除所有数的最大数;最小公倍数是能被所有数整除的最小数。12 和 18 的最大公约数是 6,最小公倍数是 36。
GCD、GCF 和 HCF 一样吗?
一样。它们都是最大公约数的英文名称。
最多可以输入多少个数?
没有数量限制,会两两依次计算。质因数分解显示前 12 个数。