輾轉相除法(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;
}