c++求两个数的最小公倍数

假设要求的两个数为a和b，它们的最小公倍数为lcm(a,b)。

最小公倍数的求法有多种，以下介绍两种常见的方法：

方法一：因数分解法

1. 对a和b进行因数分解，将其分解为质因数的乘积。

2. 将两个数的质因数分解结果合并，合并后的结果中，每个质因数的指数为两个数中该质因数指数的较大值。

3. 将合并后的质因数乘积即为a和b的最小公倍数。

例如，求12和18的最小公倍数：

12 = 2^2 × 3

18 = 2 × 3^2

将它们的质因数分解结果合并，得到：

12 = 2^2 × 3^1

18 = 2^1 × 3^2

合并后的结果为：

2^2 × 3^2 = 36

因此，12和18的最小公倍数为36。

方法二：辗转相除法

1. 用a和b的较大值除以较小值，得到商q和余数r。

2. 如果余数r为0，则最小公倍数为a和b的乘积除以最大公约数gcd(a,b)。

3. 如果余数r不为0，则将较小值变为原来的余数，较大值变为原来的除数，继续执行步骤1。

例如，求12和18的最小公倍数：

12 ÷ 18 = 0 余12

18 ÷ 12 = 1 余6

12 ÷ 6 = 2 余0

最大公约数为6，因此最小公倍数为12×18÷6=36。

以上两种方法都可以求得最小公倍数，但方法一适用于小数较小的数，方法二适用于数较大的情况。