最大公約數與最小公倍數：從暴力枚舉到輾轉相除法的算法演進

求最大公約數（GCD）與最小公倍數（LCM）是程式設計入門必修課。本文從數學關係出發，層層遞進展示三種算法實現，並探討大數場景下的擴展思路。

數學基石：GCD 與 LCM 的關係

設兩數 m, n，最大公約數為 a，則：

m = b * a
n = c * a
→ 最小公倍數 = a * b * c = m * n / a

因此 LCM(m,n) = m * n / GCD(m,n)，核心問題歸結為求 GCD。

算法 1：暴力枚舉（教學用，生產禁用）

int gcd_brute(int m, int n) {
    int smaller = min(m, n);
    int gcd = 1;
    for (int i = 2; i <= smaller; i++)
        if (m % i == 0 && n % i == 0) gcd = i;
    return gcd;
}

複雜度：O(min(m,n))，大數時極慢。

算法 2：輾轉相除法（歐幾里得算法）—— 標準解

核心定理：gcd(m, n) = gcd(n, m % n)，反覆替換直到餘數為 0。

int gcd_euclid(int m, int n) {
    while (n != 0) {
        int r = m % n;
        m = n;
        n = r;
    }
    return m;
}

// 遞歸版
int gcd_recursive(int m, int n) {
    return n == 0 ? m : gcd_recursive(n, m % n);
}

複雜度：O(log min(m,n))，極快，為工業標準實現。

算法 3：更相減損術（中國古算法，適合大整數/無除法硬體）

int gcd_subtract(int m, int n) {
    while (m != n) {
        if (m > n) m -= n;
        else n -= m;
    }
    return m;
}

《九章算術》記載，僅用減法，原理同輾轉相除，適合大整數模擬或無除法指令架構。

完整工程級實現

#include 
#include 

// 64 位支援
int64_t gcd(int64_t m, int64_t n) {
    assert(m && n);
    while (n) { int64_t r = m % n; m = n; n = r; }
    return m;
}

int64_t lcm(int64_t m, int64_t n) {
    assert(m && n);
    return m / gcd(m, n) * n;  // 先除後乘，防溢出
}

大數（> 64 位）場景擴展思路

Stein 算法（二進制 GCD）實現

int64_t gcd_stein(int64_t u, int64_t v) {
    if (u == 0) return v;
    if (v == 0) return u;
    int shift = __builtin_ctzll(u | v);
    u >>= __builtin_ctzll(u);
    do {
        v >>= __builtin_ctzll(v);
        if (u > v) { int64_t t = v; v = u; u = t; }
        v -= u;
    } while (v);
    return u << shift;
}

面試/考試加分點總結

1. 能推導 LCM = m*n/GCD 並處理溢出（先除後乘）。
2. 熟寫迭代版歐幾里得，說明為何優於遞歸（無棧溢出風險）。
3. 知曉更相減損術與 Stein 算法，能說明適用場景。
4. 考慮邊界：m=0 或 n=0、負數處理（取絕對值）、大數擴展。
5. 能分析時間複雜度：O(log min(m,n)) 及其證明關鍵（斐波那契數列最壞情況）。

總結

GCD/LCM 看似簡單，實則蘊含豐富算法演進史：從暴力枚舉 → 輾轉相除 → 更相減損 → 二進制 GCD。工程實踐中，**迭代版歐幾里得算法配合 64 位整型與先除後乘防溢出** 已覆蓋 99% 場景。面對極大整數，引入成熟大整數庫並採用 Stein 算法是務實之選。掌握這條演進脈絡，不僅能寫出正確高效代碼，更能在面試中展現算法素養深度。