求最大公约数 —— 辗转相除法 & 更相减损术

求最大公约数的常用方法有辗转相除法和更相减损术。

1. 辗转相除法

又叫欧几里得算术，该算法基于如下定理：

两个正整数 a 和 b（a > b），它们的最大公约数等于 a 除以 b 的余数 c 和 b 之间的最大公约数。

代码如下：

function gcd(a, b) {
  if (a % b === 0) {
    return b
  } else {
    return gcd(b, a % b)
  }
}

2. 更相减损术

则出自于中国古代的《九章算术》，其原理如下：

两个正整数 a 和 b（a > b），它们的最大公约数等于 a-b 的差值 c 和较小数 b 的最大公约数。

代码如下：

function gcd(a, b) {
  if (a === b) {
    return a
  } else if (a > b) {
    return gcd(b, a - b)
  } else {
    return gcd(a, b - a)
  }
}

3. 比较

辗转相除法利用的是取模（%）运算，时间复杂度近似 O(log(max(a, b)))；更相减损术利用的求两数差值，算法性能不稳定，最坏时间复杂度为 O(max(a, b)))。

辗转相除法取模运算性能差，但是收敛的速度比更相减损术快。