最大公約數與最小公倍數：輾轉相除法、輾轉相減法 C 語言實現

最大公約數 (GCD) 兩種經典算法

1. 輾轉相除法（歐幾里得算法）—— 推薦，效率最高

原理：gcd(m, n) = gcd(n, m % n)，直到餘數為 0，當前除數即為最大公約數。

int GCD(int m, int n) {
    int tem;
    if (m < n) { tem = m; m = n; n = tem; }  // 確保 m >= n
    while (n != 0) {
        tem = m % n;
        m = n;
        n = tem;
    }
    return m;
}

• 時間複雜度：O(log min(m,n))。
• 遞歸寫法同樣簡潔：return n == 0 ? m : GCD(n, m % n);

2. 輾轉相減法（更相減損術）—— 理解原理用，實際較慢

原理：gcd(m, n) = gcd(n, m - n)（假設 m > n），反覆相減直到兩數相等。

int GCD(int m, int n) {
    int tem;
    while (n != 0) {
        if (m < n) { tem = m; m = n; n = tem; }
        tem = m - n;
        m = n;
        n = tem;
    }
    return m;
}

• 當兩數差距極大時需大量迭代，效率遠低於相除法。
• 適合不支援取模運算的極簡環境（如某些硬體邏輯）。

最小公倍數 (LCM)

數學關係：LCM(m, n) = m * n / GCD(m, n)。

int LCM(int m, int n) {
    return m * n / GCD(m, n);
}

⚠️ **溢出風險**：m * n 可能超出 int 範圍。工程上建議：

int LCM(int m, int n) {
    return m / GCD(m, n) * n;  // 先除後乘，降低溢出機率
}
// 或使用 long long：
long long LCM(long long m, long long n) {
    return m / GCD(m, n) * n;
}

完整可測試程式

#include 

int GCD(int m, int n) {
    if (m < n) { int t = m; m = n; n = t; }
    while (n) { int t = m % n; m = n; n = t; }
    return m;
}

int LCM(int m, int n) {
    return m / GCD(m, n) * n;
}

int main() {
    int a, b;
    printf("Input two positive integers: ");
    if (scanf("%d %d", &a, &b) == 2 && a > 0 && b > 0) {
        printf("GCD = %d\n", GCD(a, b));
        printf("LCM = %d\n", LCM(a, b));
    } else {
        printf("Invalid input.\n");
    }
    return 0;
}

擴展：多個數的 GCD/LCM

int GCD_array(int *arr, int n) {
    int g = arr[0];
    for (int i = 1; i < n; i++) g = GCD(g, arr[i]);
    return g;
}

int LCM_array(int *arr, int n) {
    int l = arr[0];
    for (int i = 1; i < n; i++) l = LCM(l, arr[i]);
    return l;
}

應用場景

• 分數加減運算（通分）。
• 周期性事件同步（如齒輪轉動、任務調度）。
• 密碼學（RSA 金鑰生成需模逆，核心用擴展歐幾里得）。
• 簡化比例、網格對齊、圖形學纹理重複計算。