輾轉相除法

輾轉相除法, 又名歐幾里德算法（Euclidean algorithm）乃求兩個正整數之最大公因數的算法。它是已知最古老的算法, 其可追溯至前300年。它首次出現於歐幾里德的《幾何原本》（第VII卷，命题i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。它並不需要把二數作質因數分解。

[编辑] 算法

輾轉相除法是利用以下性質來確定两个正整数 a 和 b 的最大公因數的：

1. 若 r 是 a ÷ b 的餘數, 則

   gcd(a,b) = gcd(b,r)

2. a 和其倍數之最大公因數為 a。

另一種寫法是：

1. a ÷ b，令r为所得餘数（0≤r＜b）

   若 r = 0，算法结束；b 即为答案。

2. 互换：置 a←b，b←r，并返回第一步。

[编辑] 虛擬碼

這個算法可以用递归寫成如下:

function gcd(a, b) {
    if (a 不整除 b)
        return gcd(b, a mod b);
    else
        return a;
}

或純使用迴圈:

function gcd(a, b) {
    define r as integer;
    while b ≠ 0 {
        r := a mod b;
        a := b;
        b := r;
    }
    return a;
}

其中“a mod b”是指取 a ÷ b 的餘數。

例如，123456 和 7890 的最大公因數是 6, 這可由下列步驟看出：

只要可計算餘数都可用輾轉相除法來求最大公因數。這包括多項式、複整數及所有歐幾里德定義域（Euclidean domain）。

輾轉相除法的運算速度為 O(n²)，其中 n 為輸入數值的位數。

[编辑] 參考資料

1. 高德纳,《计算机程序设计艺术》, volume 1 and volume 2. Addison-Wesley.

[编辑] 外部链接

• Euclid's Algorithm at cut-the-knot
• Binary Euclid's Algorithm (Java) at cut-the-knot
• Euclid's Game (Java) at cut-the-knot
• 埃立克·魏爾斯史甸在MathWorld中所描述之Euclidean Algorithm。

• Euclid's algorithm at PlanetMath.