C語言輾轉相除法求最大公約數（GCD）完整實現與解析

輾轉相除法（歐幾里得算法）求最大公約數

輾轉相除法是求兩數最大公約數（GCD）的經典高效演算法，特別適合大整數。核心定理：

若 a = b×q + c，則 gcd(a, b) = gcd(b, c)

演算法步驟演示

例：求 15750 與 27216 的 GCD

27216 = 15750 × 1 + 11466  → gcd(15750, 27216) = gcd(15750, 11466)
15750 = 11466 × 1 +  4284  → gcd(15750, 11466) = gcd(11466, 4284)
11466 =  4284 × 2 +  2898  → gcd(11466, 4284)  = gcd(4284, 2898)
 4284 =  2898 × 1 +  1386  → gcd(4284, 2898)   = gcd(2898, 1386)
 2898 =  1386 × 2 +   126  → gcd(2898, 1386)   = gcd(1386, 126)
 1386 =   126 × 11 +     0  → gcd(1386, 126)    = 126

結果：GCD = 126

C 語言完整實現

#include 

int gcd(int a, int b) {
    // 確保 a <= b
    if (a > b) {
        int tmp = a; a = b; b = tmp;
    }
    // 輾轉相除核心循環
    while (b % a != 0) {
        int r = b % a;
        b = a;
        a = r;
    }
    return a;
}

int main() {
    int a, b;
    printf("請輸入兩個正整數: ");
    scanf("%d %d", &a, &b);
    printf("最大公約數: %d\n", gcd(a, b));
    return 0;
}

關鍵點解析

• 遞歸版本：return (b % a == 0) ? a : gcd(b % a, a); 更簡潔
• 時間複雜度：O(log min(a,b))，極快
• 擴展應用：求最小公倍數 LCM = a × b / GCD；解不定方程；RSA 金鑰生成
• 邊界處理：輸入 0 時 GCD 為另一數；負數取絕對值

遞歸與迭代對比

生產環境建議使用迭代版本，避免深度遞歸棧溢出風險。