C 語言基礎演算法：最大公約數與最小公倍數（輾轉相除法）

C 語言基礎演算法：最大公約數與最小公倍數（輾轉相除法）

輾轉相除法（Euclidean Algorithm）是求兩整數最大公約數（GCD）的經典演算法，最小公倍數（LCM）則可由公式 LCM = (m * n) / GCD 快速得到。

演算法原理

1. 確保 m >= n，否則交換。
2. 計算餘數 r = m % n。
3. 若 r == 0，則 n 即為 GCD。
4. 否則令 m = n, n = r，重複步驟 2~3。

完整 C 程式碼

#include <stdio.h>

int main(void) {
    int m, n, r, t, product;

    printf("輸入兩整數：");
    scanf("%d %d", &m, &n);

    // 確保 m >= n
    if (n > m) {
        t = m; m = n; n = t;
    }

    product = m * n; // 儲存乘積供 LCM 使用

    while ((r = m % n) != 0) {
        m = n;
        n = r;
    }

    printf("最大公約數：%d\n", n);
    printf("最小公倍數：%d\n", product / n);

    return 0;
}

執行範例

輸入兩整數：48 18
最大公約數：6
最小公倍數：144

複雜度與延伸

• 時間複雜度：O(log min(m,n))，極為高效。
• 遞迴寫法：int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
• 擴展：Stein 演算法（二進制 GCD）避免除法運算，適合底層優化。
• 注意：m * n 可能溢位 int，大數場景請用 long long 或先除後乘：LCM = m / gcd * n。