C 語言函數調用實戰：輾轉相除法求最大公約數與最小公倍數

C 語言函數調用實戰：輾轉相除法求最大公約數與最小公倍數

最大公約數（GCD）與最小公倍數（LCM）是數論基礎問題，C 語言通過函數封裝可實現清晰、可復用的解決方案。本文採用歐幾里得算法（輾轉相除法）實現 GY() 與 GB() 兩函數協作。

算法原理

• GCD：gcd(a,b) = gcd(b, a%b)，直到餘數為 0，當前除數即為最大公約數。
• LCM：利用公式 lcm(a,b) = a*b / gcd(a,b)，注意防止溢出可先除後乘。

完整代碼實現

#include 

// 最大公約數
int GY(int m, int n) {
    int t, r;
    if (n > m) { t = m; m = n; n = t; } // 確保 m >= n
    while ((r = m % n) != 0) {
        m = n;
        n = r;
    }
    return n;
}

// 最小公倍數
int GB(int m, int n) {
    // 先除後乘防溢出：m / GY(m,n) * n
    return m / GY(m, n) * n;
}

int main() {
    int x, y, gys, gbs;
    printf("輸入兩個正整數: ");
    scanf("%d%d", &x, &y);
    gys = GY(x, y);
    gbs = GB(x, y);
    printf("%d 和 %d 的最大公約數是：%d\n", x, y, gys);
    printf("%d 和 %d 的最小公倍數是：%d\n", x, y, gbs);
    return 0;
}

關鍵點解析

1. 參數順序無關性：函數內部自動交換保證 m >= n，調用者無需關心大小順序。
2. 避免溢出：GB 中採用 m / GY * n 而非 m * n / GY，顯著降低中間結果溢出風險。
3. 函數復用：GB 直接調用 GY，邏輯解耦，維護性強。
4. 邊界處理：若輸入包含 0，GY 返回非零數，GB 返回 0（符合數學定義）。

擴展：遞歸版 GCD

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

應用場景

• 分數運算約分（分子分母同除 GCD）。
• 周期性事件同步週期計算（LCM）。
• 密碼學算法（RSA 密鑰生成需大數 GCD）。