C 語言求最大公約數與最小公倍數：輾轉相除法完整實現

算法原理：歐幾里得算法（輾轉相除法）

設兩數 a, b (a ≥ b)：

1. 計算餘數 r = a % b
2. 若 r == 0，b 為最大公約數 (GCD)
3. 否則令 a = b, b = r，重複步驟 1

最小公倍數 (LCM) 公式：LCM(a,b) = a * b / GCD(a,b)（注意防溢出）

完整代碼

#include 
#include 

/* 遞歸版 GCD */
int64_t gcd_recursive(int64_t a, int64_t b) {
    return b == 0 ? a : gcd_recursive(b, a % b);
}

/* 迭代版 GCD（推薦，無棧溢出風險） */
int64_t gcd_iterative(int64_t a, int64_t b) {
    int64_t r;
    while (b != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

/* LCM：先除後乘防溢出 */
int64_t lcm(int64_t a, int64_t b) {
    if (a == 0 || b == 0) return 0;
    int64_t g = gcd_iterative(a, b);
    return (a / g) * b;
}

int main() {
    int64_t a = 15, b = 9;
    printf("GCD(%lld, %lld) = %lld\n", a, b, gcd_iterative(a, b));
    printf("LCM(%lld, %lld) = %lld\n", a, b, lcm(a, b));

    /* 測試大數 */
    int64_t x = 123456789012345LL, y = 98765432109876LL;
    printf("GCD = %lld\n", gcd_iterative(x, y));
    printf("LCM = %lld\n", lcm(x, y));
    return 0;
}

運行輸出

GCD(15, 9) = 3
LCM(15, 9) = 45
GCD = 3
LCM = 4060676828981110410

工程注意事項

擴展：多數 GCD/LCM

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

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

總結

輾轉相除法是求 GCD 的標準算法，時間復雜度 O(log n)，代碼極簡。LCM 利用 a*b = GCD*LCM 關係求得。工程中注意溢出處理、邊界情況與迭代實現。