最大公约数和最小公倍数
一、最大公约数
1. 是什么：
首先来回忆一下什么叫最大公约数：指两个或多个整数共有约数中最大的一个。比如60和24，60的约数有[1,2,3,4,5,6,10,12,15,20,30,60]，24的约数有[1,2,3,4,6,8,12,24]，他们共同的约数有[1,2,3,4,6,12]，共同约数种最大的是12，所以最大公约数就是12。
2. 如何求最大公约数？
在数学中，我们用分解质因数和短除法来求解，如下图，就是百度经验上用短除法求最大公约数和最小公倍数的一个过程。
短除法
那么用程序如何实现呢？
其实如果要用程序实现短除法求解，可能不是那么简单。我们可以用另一种方法，叫做辗转相除法，又叫欧几里得算法。
3. 欧几里得算法求最大公约数：
我们用(A, B)表示求A(较大的那个数)和B(较小的那个数)的最大公约数。欧几里得算法的公式如下：
- 首先让
A / B = C ~ D，如果余数D为0，那么B就是最大公约数； - 如果D不为0，那么就让除数和余数继续做上面的运算，即
B / D = E ~ F，直到余数为0，此时的除数就是最大公约数。
欧几里得算法求(60, 24)的最大公约数步骤如下：
-
60 / 24 = 2 ~ 12，所以(60, 24) = (24, 12)； -
24 / 12 = 2 ~ 0，所以(60, 24) = (24, 12) = 12
代码实现：
public static int euclid(int a, int b){
if (a == b){
return a;
}
int dividend = Math.max(a, b); // 被除数
int divisor = Math.min(a, b); // 除数
int remainder = dividend % divisor; // 余数
while (remainder != 0){
dividend = divisor;
divisor = remainder;
remainder = dividend % divisor;
}
return divisor;
}
4. 更相减损术求最大公约数：
这是九章算术里面的求最大公约数的方法，我们用(A, B)表示求A(较大的那个数)和B(较小的那个数)的最大公约数，其步骤如下：
- 首先判断A和B是否都是偶数，如果是，同时用2约分，要记住这一步约掉了几个2；
- 当A和B不同时为偶数的时候，让
A - B = C，当B和C相等时，C再乘以第一步约掉的2，约掉了几个就乘以几个，结果就是最大公约数； - 如果B和C不相等，那就看B和C谁更大，用更大的那个做被减数，更小的那个做减数，继续相减，直到减数和差相等。
更相减损术求(60, 24)的最大公约数步骤如下：
-
60 / 2 / 2 = 15，24 / 2 / 2 = 6； -
15 - 6 = 9； -
9 - 6 = 3； -
6 - 3 = 3；
此时减数和差相等了，所以最大公约数就是3 * 2 * 2 = 12。
代码实现：
public static int moreExclude(int a, int b){
if (a == b){
return a;
}
int minute = Math.max(a, b); // 被减数
int minus = Math.min(a, b); // 减数
int count = 0;
while (minute % 2 == 0 && minus % 2 == 0){
minute = minute / 2;
minus = minus / 2;
count ++;
}
int difference = minute - minus; // 差
while (difference != minus){
minute = Math.max(minus, difference);
minus = Math.min(minus, difference);
difference = minute - minus;
}
return (int) (Math.pow(2, count) * difference);
}
更相减损术代码看起来更复杂，多了一个while循环，实际上在数字不是很大的情况下，效率可能差不多，因为计算机做减法是比做除法更快的。但是当数字很大时，显然除法循环的次数更少，可以更快地得到结果。
二、最小公倍数
求出了最大公约数，求最小公倍数就很简单了，因为存在如下公式：
假如(a, b)的最大公约数是m，那么最小公倍数n = a * b / m。所以，要求最小公倍数，可以先用上述方法求出最大公约数。
