C 語言入門實作：輾轉相除法求最大公約數 (GCD)

從暴力列舉到歐幾里得演算法：最大公約數 (GCD) 的演進與 C 實作

最大公約數 (Greatest Common Divisor, GCD) 是兩個或多個整數共有因子中最大者。本文對比三種求解思路：暴力列舉法、輾轉相除法 (遞迴/迭代)、更相減損法，並給出標準 C 實作與測試主程式。

方法一：暴力列舉法 (教學用，效能差)

思路：從 min(a,b) 向下遞減，找到第一個能整除兩數的值。

int gcd_brute(int a, int b) {
    int min = a < b ? a : b;
    for (int i = min; i >= 1; i--) {
        if (a % i == 0 && b % i == 0)
            return i;
    }
    return 1;
}
// 時間複雜度 O(min(a,b))，大數時極慢

方法二：輾轉相除法 / 歐幾里得演算法 (標準解)

核心定理：gcd(a, b) = gcd(b, a % b)，直到餘數為 0，當前除數即為 GCD。

遞迴版

int gcd_recursive(int a, int b) {
    return b == 0 ? a : gcd_recursive(b, a % b);
}

迭代版 (推薦，無棧溢位風險)

int gcd_iterative(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

時間複雜度 O(log min(a,b))，極快。
證明直觀：a = q*b + r，任何同時整除 a,b 的數必整除 r，反之亦然，故公約數集合不變。

方法三：更相減損法 (《九章算術》，適合不支援取模的場景)

int gcd_subtraction(int a, int b) {
    while (a != b) {
        if (a > b) a -= b;
        else b -= a;
    }
    return a;
}
// 最壞情況 O(max(a,b)) (如連續費波納契數)，但無需除法指令

完整可執行程式

#include 
#include 

// 迭代版歐幾里得演算法
int gcd(int a, int b) {
    a = abs(a); b = abs(b); // 處理負數
    while (b) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    long long a, b;
    printf("輸入兩個整數 (空格分隔，Ctrl+C 結束):\n");
    while (scanf("%lld %lld", &a, &b) == 2) {
        printf("GCD(%lld, %lld) = %d\n", a, b, gcd((int)a, (int)b));
    }
    return 0;
}

測試樣例

擴充：多數 GCD 與最小公倍數 (LCM)

// 多數 GCD
int gcd_array(int arr[], int n) {
    int res = arr[0];
    for (int i = 1; i < n; i++)
        res = gcd(res, arr[i]);
    return res;
}

// LCM 公式：lcm(a,b) = |a*b| / gcd(a,b) (注意溢位，先除後乘)
long long lcm(long long a, long long b) {
    return a / gcd((int)a, (int)b) * b;
}

常見錯誤

• 未處理 b=0 導致除零錯誤 (迴圈條件 while(b) 天然避免)。
• 負數輸入未取絕對值，導致餘數為負、迴圈不收斂 (C 語言 % 餘數號同被除數)。
• 遞迴版在極深遞迴 (極大費波納契數) 可能棧溢位，實務首選迭代版。

輾轉相除法是數論基石，亦是 RSA 加密、分數約分、中國剩餘定理、擴展歐幾里得演算法的核心子程序。熟練掌握其迭代實作與邊界處理，是演算法基本功的重要指標。