本文将介绍最大公约数和最小公倍数的求法，以及辗转相除法的原理。

一、最大公约数

正整数 a 与 b 的最大公约数是指 a 与 b 的所有公约数中最大的那一个公约数。

例如：4 和 6 的最大公约数为 2 ，3 和 9 的最大公约数为 3 。

求解最大公约数常用欧几里得算法，即辗转相除法。辗转相除法基于这样一个原理：设 a、b 均为正整数，这 a 与 b 的最大公约数等于 b 与 a % b 的最大公约数。

证明：

• 设 a = k * b + r ，其中 k 和 r 分别为 a 除以 b 得到的商和余数，则有 r = a - k * b 。

  设 d 为 a 和 b 的一个公约数。那么由 r = a - k * b 得 d 也是 r 的一个约数。（ a 可以被 r 整除，k * b 也可以被 r 整除）

  又 d 是任意一个公约数，因此 a 和 b 的公约数都是 b 和 a % b 的公约数。

• 同理证得 b 和 a % b 的公约数都是 a 和 b 的公约数。

• 因此 a 和 b 的公约数与 b 和 a % b 的公约数全部相等，故最大公约数也相等。

研究此定理发现，若 a < b ，那么定理的结果是交换 a 和 b ；若 a > b ，那么通过这个定理可以将数据规模缩小。

另一个重要结论： 0 和任意一个整数的最大公约数都是整数本身。

解题代码：

无需交换 a 和 b ，因为它会自己交换

int gcd(int a, int b){
	if (b == 0)    return a;
	else    return gcd(b, a % b);
}

更简洁写法：

int gcd(int a, int b){
	return !b ? a : gcd(b, a % b);
}

​

二、最小公倍数

正整数 a 和 b 的最小公倍数是指 a 和 b 的所有公倍数中最小的那一个公倍数。

例如：

4 和 6 的最小公倍数是 12 ；

3 和 9 的最小公倍数是 9 ；

最小公倍数的求解在最大公约数的基础上进行，假设 a 和 b 的最大公约数为 d ，则 a 和 b 的最小公倍数是 a * b / d 。

更恰当的写法是 a / d * b ，防止数据过大而溢出。

​

参考

• 算法笔记