计算两个数的最大公约数可以使用辗转相除法。

辗转相除法

最大公约数 - 图1
有了这条定理，求最大公约数就变得简单了。我们可以使用递归的方法把问题逐步简化。
首先，计算出 a 除以 b 的余数 c ，把问题转化成求 b 和 c 的最大公约数；然后计算出 b 除以 c 的余数 d ，把问题转化成求 c 和 d 的最大公约数；再计算出 c 除以 d 的余数 e ，把问题转化成求 d 和 e 的最大公约数……
以此类推，逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算，直到两个数可以整除，或者其中一个数减小到 1 为止。

  1. public static int getGreatestCommonDivisor(int a, int b) {
  2.     int big = Math.max(a, b);
  3.     int small = Math.min(a, b);
  4.     if (big % small == 0) {
  5.         return small;
  6.     }
  7.     return getGreatestCommonDivisor(big % small, small);
  8. }

有一个问题，当两个整数较大时，做 a%b 取模运算的性能会比较差。

更相减损术

原理：
最大公约数 - 图2。
例如 10 和 25，25 减 10的差是 15，那么 10 和 25 的最大公约数，等同于 10 和 15 的最大公约数。
由此，我们同样可以通过递归来简化问题。首先，计算出 a 和 b 的差值 c （假设 a ＞b），把问题转化成求 b 和 c 的最大公约数；然后计算出 c 和 b 的差值 d （假设 c ＞b），把问题转化成求 b 和 d 的最大公约数；再计算出 b 和 d 的差值 e （假设 b ＞d），把问题转化成求 d 和 e 的最大公约数……
以此类推，逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算，直到两个数可以相等为止，最大公约数就是最终相等的这两个数的值。

  1. public static int getGreatestCommonDivisor(int a, int b) {
  2.     if (a == b) return a;
  3.     int big = Math.max(a, b);
  4.     int small = Math.min(a, b);
  5.     return getGreatestCommonDivisor(big - small, small);
  6. }

更相减损术是不稳定的算法，当两数相差悬殊时，如计算 10000 和 1 的最大公约数，就要递归 9999 次！

位运算

对于给出的正整数 a 和 b ，不难得到如下的结论。
（从下文开始，获得最大公约数的方法getGreatestCommonDivisor被简写为gcd。）

  • 当 a 和 b 均为偶数时，最大公约数 - 图3。
  • 当 a 为偶数，b 为奇数时，最大公约数 - 图4。
  • 当 a 为奇数，b 为偶数时，最大公约数 - 图5。
  • 当 a 和 b 均为奇数时，先利用更相减损术运算一次，最大公约数 - 图6，此时 a-b 必然是偶数，然后又可以继续进行移位运算。
    1. public static int gcd(int a, int b) {
    2.   if (a == b) return a;
    3.   if ((a & 1) == 0 && (b & 1) == 0) return gcd(a >> 1, b >> 1) << 1;
    4.   else if ((a & 1) == 0 && (b & 1) != 0) return gcd(a >> 1, b);
    5.   else if ((a & 1) != 0 && (b & 1) == 0) return gcd(a, b >> 1);
    6.   else {
    7.       int big = Math.max(a, b);
    8.       int small = Math.min(a, b);
    9.       return gcd(big - small, small);
    10.   }
    11. }