最大公约数和最小公倍数

一、最大公约数

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。所以，要求最小公倍数，可以先用上述方法求出最大公约数。