如果已知 a 和 b 两个正整数,它们的最大公因数记为 GCD(a, b),最小公倍数记为 LCM(a, b)。求 a 和 b 的最大公因数和最小公倍数可以采用以下方法:
1. 求最大公因数:可以使用欧几里得算法,即不断用较小数去除较大数,直到余数为 0,此时较小数即为最大公因数。
2. 求最小公倍数:使用公式 LCM(a, b) = a * b / GCD(a, b)。
例如,给定 a = 12 和 b = 18,按照上述方法可以求得:
1. GCD(12, 18) = GCD(12, 18 % 12) = GCD(12, 6) = GCD(6, 12 % 6) = GCD(6, 0) = 6,因此 a 和 b 的最大公因数为 6。
2. LCM(12, 18) = 12 * 18 / GCD(12, 18) = 12 * 18 / 6 = 36,因此 a 和 b 的最小公倍数为 36。