首页 › Python 实例 › 最大公约数与最小公倍数

Python 最大公约数与最小公倍数

数学实例 016

题目

用辗转相除法求最大公约数(GCD),再由 LCM = a × b / GCD 求最小公倍数。

参考代码

import math

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

for a, b in [(12, 18), (54, 24), (17, 5)]:
    print(f"gcd({a}, {b}) = {gcd(a, b)}, lcm = {lcm(a, b)}  | math.gcd = {math.gcd(a, b)}")

print("多个数的最小公倍数:", math.lcm(4, 6, 10))
执行以上代码输出结果为:
gcd(12, 18) = 6, lcm = 36  | math.gcd = 6
gcd(54, 24) = 6, lcm = 216  | math.gcd = 6
gcd(17, 5) = 1, lcm = 85  | math.gcd = 1
多个数的最小公倍数: 60

代码解析

辗转相除法(欧几里得算法):gcd(a, b) = gcd(b, a mod b),直到余数为 0。Python 3.9 起 math.gcd 和 math.lcm 都支持传入多个参数。