计算最大公约数 最小公倍数

计算最大公约数和最小公倍数是数学中的基本问题，Python也提供了多种方法来解决这些问题。其中，求最大公约数可以使用辗转相除法，而求最小公倍数可以使用递归算法。

1. 求最大公约数：
- 辗转相除法是一种求最大公约数的常用方法，其基本思想是用较大数除以较小数，再用余数去除除数，如此反复，直到余数为0为止。最后的除数就是这两个数的最大公约数。
- Python代码实现：

   def gcd(a, b):
       if b == 0:
           return a
       else:
           return gcd(b, a % b)

2. 求最小公倍数：
- 最小公倍数是指两个或多个整数公有的倍数中，最小的一个公共倍数。可以通过先求出最大公约数，然后用两数之积除以最大公约数得到最小公倍数。
- Python代码实现：

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

相关问题

c计算最大公约数 最小公倍数

最大公约数是指两个或多个整数共有约数中最大的一个，而最小公倍数是指两个或多个整数公有的倍数中最小的一个。计算最大公约数和最小公倍数的方法有多种，以下是两种常见的方法：
1.辗转相除法：用较大数除以较小数，再用余数去除较小数，直到余数为0为止，此时较小数即为最大公约数，最小公倍数为两数之积除以最大公约数。
2.最大公约数和最小公倍数的关系：已知两个数a，b，最大公约数是c，则最小公倍数是a*b/c。因此，可以先求出最大公约数，再用两数之积除以最大公约数即可得到最小公倍数。

最大公约数最小公倍数计算

最大公约数（Greatest Common Divisor，简称 GCD）指的是两个或多个整数共有约数中最大的一个数。最小公倍数（Least Common Multiple，简称 LCM）指的是两个或多个整数公有的倍数中最小的一个数。下面是两个整数的 GCD 和 LCM 的计算方法：

假设两个整数分别为 a 和 b，其中 a > b。

1. 计算 a 和 b 的余数 r = a % b。
2. 如果 r = 0，则 b 就是最大公约数，a 和 b 的乘积除以最大公约数就是最小公倍数。
3. 如果 r ≠ 0，则令 a = b，b = r，然后返回第 1 步。

可以使用递归或迭代的方法实现上述算法。下面是 Python 代码示例：

# 计算两个整数的最大公约数和最小公倍数
def gcd_lcm(a, b):
    # 计算最大公约数
    x, y = a, b
    while y != 0:
        x, y = y, x % y
    gcd = x
    # 计算最小公倍数
    lcm = a * b // gcd
    return gcd, lcm

# 示例
print(gcd_lcm(12, 20))  # 输出 (4, 60)