辗转相除法(Euclidean algorithm)

辗转相除法是求两数的最大公因数(greatest common divisor,GCD)的演算法，也被称为「欧几里德演算法」(欧式演算法），辗转相除法只要反覆进行除法，就能求出最大公因数。即使运算的两个数很大，也能用明确步骤有效率地求出最大公因数。

使用Python实现GCD

方法1：

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

方法2：

import math

print(math.gcd(1071,462)) #21

使用JavaScript实现GCD

function gcd(x, y) {
 if ((typeof x !== 'number') || (typeof y !== 'number')) 
    return false;
  x = Math.abs(x);
  y = Math.abs(y);
  while(y) {
    var t = y;
    y = x % y;
    x = t;
  }
  return x;
}