C 語言計算兩數最小公倍數（LCM）的兩種高效方法

方法一：輾轉相除法（歐幾里得演算法）求 GCD，再推導 LCM

最小公倍數與最大公約數關係：LCM(a,b) = |a*b| / GCD(a,b)。此法效率最高，時間複雜度 O(log min(a,b))。

#include 
#include 

long long gcd(long long a, long long b) {
    while (b) {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

long long lcm(long long a, long long b) {
    return llabs(a) / gcd(a, b) * llabs(b);  // 先除後乘避免溢位
}

int main() {
    long long a, b;
    scanf("%lld %lld", &a, &b);
    printf("%lld\n", lcm(a, b));
    return 0;
}

方法二：暴力枚舉法（原始碼邏輯）

原始碼採用從較大數開始，以其倍數測試是否能被較小數整除：

#include 

int main() {
    int a, b, i = 1, temp, lcm;
    scanf("%d %d", &a, &b);
    if (a > b) { temp = a; a = b; b = temp; }  // 確保 a <= b

    lcm = b;
    if (b % a != 0) {
        while (lcm % a != 0) {
            lcm = b * i;
            i++;
        }
    }
    printf("%d", lcm);
    return 0;
}

效能比較與建議

避坑指南

1. 溢位處理：a * b 可能超出 int 範圍，建議用 long long 並採用 a / gcd * b 順序運算。
2. 零與負數：LCM 定義域為非零整數，實際工程需加入參數檢查。
3. 標準庫支援：C++17 起 提供 std::lcm，C23 也將納入標準。

總結

雖然暴力枚舉法邏輯直觀，但實際開發中**強烈建議使用輾轉相除法**，並注意資料型別選擇與溢位防護。