C語言求最大公約數與最小公倍數的多種演算法實現

前言

在C語言程式設計中，求兩個整數的最大公約數（GCD）與最小公倍數（LCM）是經典的基礎練習。本文將介紹四種常見演算法：窮舉法（遞減與遞增）、輾轉相除法（歐幾里得演算法）與相減法（更相減損術），並提供完整原始碼與邏輯分析，幫助初學者理解不同演算法的效率差異。

一、窮舉法（遞減搜尋）

思路：從兩數中較小者（或其中一數）開始遞減，尋找第一個能同時整除兩數的整數，即為最大公約數。

#include <stdio.h>

int main() {
    int m, n, i;
    scanf("%d%d", &m, &n);
    for (i = (m < n ? m : n); ; i--) {
        if (m % i == 0 && n % i == 0) break;
    }
    printf("GCD=%d, LCM=%d\n", i, m * n / i);
    return 0;
}

特點：直觀易懂，但當數值較大時效率極低，時間複雜度 O(min(m,n))。

二、窮舉法（遞增搜尋）

思路：從 1 遞增至兩數中的較小值，記錄最後一個能同時整除兩數的整數。

#include <stdio.h>

int main() {
    int m, n, t, i;
    scanf("%d%d", &m, &n);
    for (i = 1; i <= (m < n ? m : n); i++) {
        if (m % i == 0 && n % i == 0) t = i;
    }
    printf("GCD=%d, LCM=%d\n", t, m * n / t);
    return 0;
}

特點：同樣屬暴力解法，效率不佳，僅適合教學示範。

三、輾轉相除法（歐幾里得演算法）

思路：利用 gcd(a, b) = gcd(b, a % b) 的數學性質，反覆取餘直到餘數為 0，最後的除數即為最大公約數。此法效率極高，時間複雜度 O(log min(m,n))。

#include <stdio.h>

int main() {
    int m, n, r, t;
    scanf("%d%d", &m, &n);
    r = m * n;              // 保存乘積，用於後續計算 LCM
    t = m % n;
    while (t) {
        m = n;
        n = t;
        t = m % n;
    }
    printf("GCD=%d, LCM=%d\n", n, r / n);
    return 0;
}

範例分析：輸入 40、32
40 % 32 = 8 → 32 % 8 = 0 → GCD = 8
LCM = 40 × 32 / 8 = 160

四、相減法（更相減損術）

思路：出自《九章算術》，兩數相減，用差與較小數繼續相減，直到兩數相等，該值即為最大公約數。適合不支援取模運算的環境。

#include <stdio.h>

int main() {
    int m, n, r;
    scanf("%d%d", &m, &n);
    r = m * n;
    while (m != n) {
        if (m > n) m = m - n;
        else n = n - m;
    }
    printf("GCD=%d, LCM=%d\n", m, r / m);
    return 0;
}

範例分析：輸入 40、32
40-32=8 → 32-8=24 → 24-8=16 → 16-8=8 → 8=8 → GCD=8
LCM = 40×32/8 = 160

效能比較與建議

實際開發中強烈建議使用輾轉相除法，代碼簡潔且效能最優。