当前位置:首页>维修大全>综合>

a和b的最大公因数和最小公倍数

a和b的最大公因数和最小公倍数

更新时间:2024-01-14 17:19:12

a和b的最大公因数和最小公倍数

如果已知 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。

更多栏目