C語言實現多個數的最小公倍數（LCM）

問題描述

給定一個整數陣列，求其所有元素的最小公倍數（LCM）。

演算法原理

利用兩兩求 LCM 的性質：

LCM(a, b, c) = LCM(LCM(a, b), c)

而兩數 LCM 可通過最大公約數（GCD）計算：

LCM(a, b) = a * b / GCD(a, b)

本實現採用累積 GCD 法：先求所有數的 GCD，再將每個數除以 GCD 相乘，最後乘回 GCD，避免中間結果溢出。

代碼實現

[cpp]
#include <stdio.h>

// 獲取最大公約數（輾轉相除法）
int getGCD(int a, int b) {
    if (a % b == 0) return b;
    return getGCD(b, a % b);
}

// 計算陣列最小公倍數
int doLCM(int* array, int size) {
    int x, y, temp, gcd = array[0], i, result = 1;

    // 累積求所有數的 GCD
    for (i = 0; (i + 1) < size; i++) {
        x = gcd;
        y = array[i + 1];
        // 確保 x >= y
        if (x < y) {
            temp = y; y = x; x = temp;
        }
        gcd = getGCD(x, y);
    }

    // 每個數除以 GCD 後相乘
    for (i = 0; i < size; i++) {
        result *= array[i] / gcd;
    }
    // 最後乘回 GCD
    return result * gcd;
}

int main(void) {
    int array[3] = {144, 24, 36};
    int result = doLCM(array, 3);
    printf("%d\n", result); // 輸出 144
    return 0;
}

關鍵點

• 避免溢出：先除後乘，減少中間值大小。
• GCD 實現：遞歸版輾轉相除法，簡潔高效。
• 適用性：適用於任意長度正整數陣列。

測試結果

輸入 {144, 24, 36}，輸出 144，驗證正確。