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 都支持传入多个参数。