如何求出两个数的最大公约数和最小公倍数？

两个数的最大公约数(Greatest Common Divisor, GCD)是两个数共有的最大正整数因子。
两个数的最小公倍数(Least Common Multiple, LCM)是能够同时整除两个数的最小正整数。

求最大公约数可以使用欧几里得算法:

python
def gcd(x, y):
    if x == 0:
        return y
    if y == 0:
        return x
    if x == y:
        return x
    if x > y:
        return gcd(x-y, y)
    return gcd(x, y-x)

求最小公倍数可以使用:最小公倍数 = 两数乘积 / 最大公约数

python
def lcm(x, y):
    return x * y // gcd(x, y)

示例:

python
print(gcd(8, 12))  # 4
print(lcm(8, 12)) # 24

print(gcd(2, 6))   # 2 
print(lcm(2, 6))   # 6

结果:

4
24
2
6

所以,求最大公约数和最小公倍数的主要步骤是:

1. 求最大公约数可以使用辗转相除法,递归地计算两个数的余数,直到余数为 0。
2. 最小公倍数 = 两数乘积 / 最大公约数。
3. 特殊情况,如果两个数有一个为 0,则:

• 最大公约数为另一个非 0 数。
• 最小公倍数为 0。