🔢 最大公约数与最小公倍数计算器
使用辗转相除法计算GCD和LCM
最大公约数与最小公倍数使用说明
核心公式与算法
【辗转相除法求GCD】
gcd(a,b):
while b ≠ 0:
t = b
b = a mod b
a = t
return a
【GCD与LCM的关系】
LCM(a,b) = |a × b| / GCD(a,b)
重要性质：GCD(a,b) × LCM(a,b) = a × b实际计算案例
📋
【案例1】求24和36的GCD和LCM
辗转相除过程：
36 ÷ 24 = 1 余 12
24 ÷ 12 = 2 余 0
余数为0时，GCD = 12
LCM = 24 × 36 ÷ 12 = 72
【案例2】求15和28的GCD和LCM
辗转相除过程：
28 ÷ 15 = 1 余 13
15 ÷ 13 = 1 余 2
13 ÷ 2 = 6 余 1
2 ÷ 1 = 2 余 0
GCD = 1（互质）
LCM = 15 × 28 ÷ 1 = 420
【案例3】求12和18的GCD和LCM用于分数通分
GCD(12,18)=6, LCM(12,18)=36
5/12 + 7/18 = 15/36 + 14/36 = 29/36
常见注意事项
💡
- 输入必须为正整数，不支持0和负数（GCD定义域为自然数）
- 当两数互质时（如15和28），GCD=1，LCM等于两数之积
- 辗转相除法的时间复杂度为O(log min(a,b))，即使对大数也极快
- 对于三个及以上数字，可先算前两个的GCD，再与第三个继续算
- 质数的GCD一定是1（除非两数相同）
应用场景列表
- - 分数运算：通分时找最小公倍数作为公分母，约分时找最大公约数
- - 日程安排：多个周期性事件的最小公共间隔（如轮班表设计）
- - 密码学：RSA加密算法依赖大数分解和GCD计算
- - 齿轮设计：计算齿轮组的最小齿数使传动比精确
- - 音乐理论：计算节拍频率比、音程和谐度分析
与相关工具的关系
GCD/LCM计算器与分数计算器紧密配合——分数加减需要先通分（用LCM），结果需要约分（用GCD）。排列组合计算中也常涉及GCD，比如化简组合数C(n,k)的结果。此外，在解不定方程、判断互质关系、以及中国剩余定理等问题中，GCD都是基础工具。掌握GCD/LCM的计算方法是深入理解数论的第一步。