怎么求最小公倍数和最大公约数

计算两个数的最大公约数（Greatest Common Divisor, GCD）和最小公倍数（Least Common Multiple, LCM）是基础的数学运算，在计算机编程中也很常见。以下是常用的几种方法：

1. **欧几里得算法**（Euclidean Algorithm）用于求解GCD。该算法基于这样一个事实：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。例如，gcd(a, b) = gcd(b, a mod b)。

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

2. **辗转相除法**是欧几里得算法的一种直观解释。也可以通过循环直到余数为0，然后用除数作为新的a，之前除数的余数作为新的b，继续这个过程。

3. 对于LCM，有一个公式是：`lcm(a, b) = |a * b| / gcd(a, b)`，因为两数乘积等于它们的最大公约数和最小公倍数的乘积。

4. **质因数分解法**：首先分解出两个数的所有质因数，然后取每个质因子的最大指数作为LCM的质因数，最小指数作为GCD的质因数。

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