欧几里得算法 - Life & Code

在数学中，辗转相除法，又称欧几里得算法（英语：Euclidean algorithm），是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第 VII 卷，命题 i 和 ii）中，而在中国则可以追溯至东汉出现的《九章算术》。
– 《辗转相除法 - 维基百科》

以上是 wikipedia 中的一段摘要，理论上欧几里得的辗转相除法实际可以计算任意多整数的最大公约数。

不过，今天主要是和大家分享一下其中一个最简单的案例，求两个整数的最大公约数。

根据 wikipedia 的解释，两个整数的最大公约数等于其中较小的数和两数的差的最大公约数，公式如下：

1
g = GCD(a, b) = GCD(b, r0) = GCD(r0, r1) = … = GCD(rN−2, rN−1) = rN−1

可能上面的描述不是很直观，那就用个例子来解释一下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
a = 1071; b = 462;

// 从1071中不断减去462直到小于462（可以减2次，即商q0 = 2），余数是147
1071 = 2 × 462 + 147

// 然后从462中不断减去147直到小于147（可以减3次，即q1 = 3），余数是21
462 = 3 × 147 + 21

// 再从147中不断减去21直到小于21（可以减7次，即q2 = 7），没有余数
147 = 7 × 21 + 0

// 此时，余数是0，所以1071和462的最大公约数是21

其实说白了就是不断的取余，直到余数为 0，就可以得出最大公约数了。

那么，能想到最直接的方式就是使用递归了，下面用Javascript实现一遍：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
const GCD = (a, b) => {
  // a 必须 大于 b
  if (b === 0) {
    return a;
  }
  let max = a;
  let min = b;
  if (max < min) {
    min = a;
    max = b;
  }
  return GCD(min, max % min);
};

文章目录