Python教程：两种求最大公约数和最小公倍数的方法

两种求最大公约数和最小公倍数的方法

在Python编程中，经常会遇到求两个数的最大公约数和最小公倍数的问题。最大公约数（Greatest Common Divisor，简称GCD）是指两个或多个整数共有约数中最大的一个数，最小公倍数（Least Common Multiple，简称LCM）是指能被两个或多个整数整除的最小的一个数。

方法一：欧几里得算法

欧几里得算法是求解最大公约数的常用方法，也称为辗转相除法。该算法基于如下观察：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。

下面是使用欧几里得算法求解最大公约数和最小公倍数的示例代码：

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
def lcm(a, b):
    return a * b // gcd(a, b)

在代码中，函数gcd()使用循环和取模操作求解最大公约数，直到其中一个数为0为止。函数lcm()则通过最大公约数求解最小公倍数，使用了整除操作。

下面是使用欧几里得算法求解最大公约数和最小公倍数的示例：

a = 12
b = 18
print("最大公约数：", gcd(a, b))
print("最小公倍数：", lcm(a, b))

运行结果：

最大公约数： 6
最小公倍数： 36

方法二：辗转相减法

辗转相减法也是求解最大公约数的一种方法。该算法基于如下观察：两个整数的最大公约数等于其中较小的数和两数差的最大公约数。

下面是使用辗转相减法求解最大公约数和最小公倍数的示例代码：

def gcd(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a
def lcm(a, b):
    return a * b // gcd(a, b)

在代码中，函数gcd()使用循环和减法操作求解最大公约数，直到两数相等为止。函数lcm()则通过最大公约数求解最小公倍数，使用了整除操作。

下面是使用辗转相减法求解最大公约数和最小公倍数的示例：

a = 12
b = 18
print("最大公约数：", gcd(a, b))
print("最小公倍数：", lcm(a, b))

运行结果：

最大公约数： 6
最小公倍数： 36

通过以上两种方法，我们可以轻松求解任意两个数的最大公约数和最小公倍数。