最大公因數 GCD Greatest Common Divisor

學習目標

理解最大公因數的概念
掌握輾轉相除法 (Euclidean Algorithm) 的原理
能夠實作遞迴和迭代版本的 GCD 演算法
理解時間複雜度分析

1. 最大公因數的基本概念

1.1 定義

最大公因數 (GCD) 是指兩個或多個整數共有約數中最大的一個。

1.2 範例

GCD(12, 18) = 6
12 的因數: 1, 2, 3, 4, 6, 12
18 的因數: 1, 2, 3, 6, 9, 18
公因數: 1, 2, 3, 6
最大公因數: 6
GCD(17, 13) = 1（互質）

1.3 應用

分數的約分
密碼學（RSA 演算法）
模運算
演算法設計

2. 計算 GCD 的方法

2.1 方法 1: 列舉法

列出所有公因數，找出最大的。

缺點: 效率低，當數字很大時不實用。

2.2 方法 2: 質因數分解

將兩個數分解為質因數，找出共同的質因數。

範例: GCD(12, 18) - 12 = 2² × 3 - 18 = 2 × 3² - 共同質因數: 2¹ × 3¹ = 6

缺點: 質因數分解本身就很困難。

2.3 方法 3: 輾轉相除法（推薦）

輾轉相除法 (Euclidean Algorithm) 是最有效的方法。

3. 輾轉相除法 (Euclidean Algorithm)

3.1 原理

關鍵性質: GCD(a, b) = GCD(b, a mod b)

其中 a mod b 是 a 除以 b 的餘數。

3.2 演算法步驟

如果 b = 0，則 GCD(a, b) = a
否則，計算 r = a mod b
遞迴計算 GCD(b, r)

3.3 範例

計算 GCD(48, 18):

步驟 1: - 48 ÷ 18 = 2 餘 12 - GCD(48, 18) = GCD(18, 12)

步驟 2: - 18 ÷ 12 = 1 餘 6 - GCD(18, 12) = GCD(12, 6)

步驟 3: - 12 ÷ 6 = 2 餘 0 - GCD(12, 6) = GCD(6, 0)

步驟 4: - GCD(6, 0) = 6（因為任何數與 0 的 GCD 是該數本身）

結果: GCD(48, 18) = 6

3.4 執行過程表

a	b	a mod b	說明
48	18	12	48 ÷ 18 = 2 ... 12
18	12	6	18 ÷ 12 = 1 ... 6
12	6	0	12 ÷ 6 = 2 ... 0
6	0	-	GCD = 6

4. 程式實作

4.1 遞迴版本

int gcd(int a, int b) {
    // 基礎情況：如果 b 為 0，則 a 就是 GCD
    if (b == 0)
        return a;

    // 遞迴呼叫：GCD(a, b) = GCD(b, a mod b)
    return gcd(b, a % b);
}

執行過程 (GCD(48, 18)):

gcd(48, 18)
  → gcd(18, 48 % 18) = gcd(18, 12)
    → gcd(12, 18 % 12) = gcd(12, 6)
      → gcd(6, 12 % 6) = gcd(6, 0)
        → 返回 6

4.2 迭代版本

int gcd(int a, int b) {
    int temp;

    // 確保 a >= b
    if (a < b) {
        temp = a;
        a = b;
        b = temp;
    }

    // 輾轉相除直到 b 為 0
    while (b != 0) {
        temp = b;
        b = a % b;
        a = temp;
    }

    return a;
}

執行過程 (GCD(48, 18)):

初始: a = 48, b = 18

迭代 1:
  temp = 18
  b = 48 % 18 = 12
  a = 18

迭代 2:
  temp = 12
  b = 18 % 12 = 6
  a = 12

迭代 3:
  temp = 6
  b = 12 % 6 = 0
  a = 6

b == 0，返回 a = 6

4.3 簡化版本（不需要交換）

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

說明: 即使 a < b，第一次迭代後也會自動交換。

範例: GCD(18, 48)

初始: a = 18, b = 48

迭代 1:
  temp = 48
  b = 18 % 48 = 18
  a = 48
  (現在 a = 48, b = 18，已經交換)

迭代 2:
  temp = 18
  b = 48 % 18 = 12
  a = 18
  ...

4.4 處理負數

int gcd(int a, int b) {
    // 取絕對值
    if (a < 0) a = -a;
    if (b < 0) b = -b;

    if (b == 0)
        return a;
    return gcd(b, a % b);
}

5. 擴展歐幾里得演算法

5.1 概念

擴展歐幾里得演算法不僅計算 GCD，還找到整數 x 和 y，使得：

ax + by = GCD(a, b)

5.2 實作

int extendedGcd(int a, int b, int *x, int *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }

    int x1, y1;
    int gcd = extendedGcd(b, a % b, &x1, &y1);

    *x = y1;
    *y = x1 - (a / b) * y1;

    return gcd;
}

6. 時間複雜度分析

6.1 理論分析

輾轉相除法的時間複雜度為 O(log min(a, b))。

原因: 每次迭代，較大的數至少減少一半。

6.2 最壞情況

費波那契數列 會產生最壞情況： - GCD(F(n), F(n-1)) 需要 n 次迭代 - 其中 F(n) 是第 n 個費波那契數

6.3 實際效能

對於 64 位元整數，最多需要約 64 次迭代
實際執行非常快速

7. 最小公倍數 (LCM)

7.1 定義

最小公倍數 (LCM) 是指兩個或多個整數公有的倍數中最小的一個。

7.2 與 GCD 的關係

LCM(a, b) = (a × b) / GCD(a, b)

7.3 實作

int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

注意: 為了避免溢位，可以寫成：

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

8. 練習題

練習題 1

使用輾轉相除法計算 GCD(100, 35)，逐步展示過程。

解答：

a	b	a mod b
100	35	30
35	30	5
30	5	0
5	0	-

結果: GCD(100, 35) = 5

練習題 2

實作一個函數，計算三個數的最大公因數。