最大公约数和最小公倍c++

最大公约数（Greatest Common Divisor，简写为GCD）是指能够整除两个或多个整数的最大整数。最小公倍数（Least Common Multiple，简写为LCM）是指能够被两个或多个整数整除的最小正整数。

有以下两种常见的方法来求解最大公约数和最小公倍数：

1. 辗转相除法：假设要求两个整数a和b的最大公约数（记为gcd(a, b)），可以通过连续用较小的数去除较大的数，直到余数为0时停止。此时较小的数即为最大公约数。
例如，计算gcd(24, 36)：
36 ÷ 24 = 1，余数为12
24 ÷ 12 = 2，余数为0
因此gcd(24, 36) = 12

最小公倍数可以通过公式 lcm(a, b) = |a * b| / gcd(a, b) 计算。
例如，计算lcm(24, 36)：
lcm(24, 36) = |24 * 36| / gcd(24, 36) = 864 / 12 = 72

2. 因数分解法：将两个数分别进行因数分解，然后取两个数分解的公共部分作为最大公约数，再将两个数分解的所有因子相乘得到最小公倍数。
例如，计算gcd(24, 36)：
24 = 2^3 * 3
36 = 2^2 * 3^2
公共部分为2^2 * 3，因此gcd(24, 36) = 2^2 * 3 = 12

计算lcm(24, 36)：
lcm(24, 36) = 2^3 * 3^2 = 72

注意：以上方法仅适用于求解两个整数的最大公约数和最小公倍数，对于多个整数的情况需要稍作扩展。