「一、最大公约数」
「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就是最大公约数；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 = C，当B和C相等时，C再乘以第一步约掉的2，约掉了几个就乘以几个，结果就是最大公约数；更相减损术求(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。所以，要求最小公倍数，可以先用上述方法求出最大公约数。
扫描二维码
联系客服
