🔢 公约数公倍数
最大公约数 GCD · 最小公倍数 LCM · 质因数分解
最大公约数 GCD · 最小公倍数 LCM · 质因数分解
常用辗转相除法（欧几里得算法）。对两个数a和b，gcd(a,b)=gcd(b,a mod b)，直到余数为0。多数的GCD = gcd(gcd(a,b),c)。
两数的LCM = |a×b| / gcd(a,b)。多数的LCM = lcm(lcm(a,b),c)。GCD和LCM也可以用质因数分解法计算。
对任意两个正整数a和b，恒有：a×b = GCD(a,b) × LCM(a,b)。即两数之积等于它们的最大公约数与最小公倍数的乘积。
如果两个数的最大公约数是1，就说它们互质。如8和9互质（gcd=1），虽然8和9都不是素数。互质的两个数最小公倍数就是它们的乘积。
比如求gcd(48,18)：48÷18=2余12，18÷12=1余6，12÷6=2余0，余数为0时的除数6就是最大公约数，即gcd=6。
分东西求最大公约数（如把糖果平均分到最多组）、求周期事件的共同周期用LCM（如两个人分别每3天和每4天值班，LCM=12天后又一起）、切分最小方块等。
先求前两个数的GCD/LCM，再与第三个数套用同样的公式。如gcd(12,18,24)=gcd(gcd(12,18),24)=gcd(6,24)=6。
可以被处理，但通常取绝对值计算，因为GCD定义为非负的。比如gcd(-12,18)按12和18算仍是6。本工具建议输入正整数。
辗转相除法是求最大公约数的经典算法，历史超过2000年。核心思想：gcd(a,b)=gcd(b, a mod b)，反复用较小的数去除较大的数，直到整除为止。
它比逐个试除公因数高效得多，尤其适合大数。也是现代计算机求GCD的标准实现。
| 步骤 | 被除数 | 除数 | 商 | 余数 |
|---|---|---|---|---|
| 第1步 | 48 | 18 | 2 | 12 |
| 第2步 | 18 | 12 | 1 | 6 |
| 第3步 | 12 | 6 | 2 | 0 |
把每个数分解为质数幂的乘积，GCD取"各质数公共幂的最小指数"，LCM取"各质数幂的最大指数"。
比如12=2²×3，18=2×3²。GCD取2¹×3¹=6；LCM取2²×3²=36。与辗转相除法结果一致。
| 数对 | GCD | LCM | 是否互质 |
|---|---|---|---|
| 12, 18 | 6 | 36 | 否 |
| 8, 9 | 1 | 72 | 是 |
| 15, 20 | 5 | 60 | 否 |
| 7, 11 | 1 | 77 | 是 |
| 24, 36 | 12 | 72 | 否 |
| 16, 24 | 8 | 48 | 否 |
| 数 | 质因数分解 | 数 | 质因数分解 |
|---|---|---|---|
| 12 | 2²×3 | 18 | 2×3² |
| 20 | 2²×5 | 24 | 2³×3 |
| 30 | 2×3×5 | 36 | 2²×3² |
| 48 | 2⁴×3 | 60 | 2²×3×5 |
1. 输入2-5个正整数。
2. 点击"添加数字"增加输入框，点击"×"删除。
3. 自动计算GCD和LCM。