C# 計算最小公倍數：輾轉相除法與多數擴展

最小公倍數 (LCM) 可透過最大公約數 (GCD) 計算：LCM(a,b) = |a×b| / GCD(a,b)。本文實作兩數 LCM 並擴展至多數情況。

核心演算法：輾轉相除法求 GCD

public int Gcd(int a, int b) {
    while (b != 0) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return Math.Abs(a);
}

public int Lcm(int a, int b) {
    if (a == 0 || b == 0) return 0;
    return Math.Abs(a / Gcd(a, b) * b); // 先除後乘避免溢位
}

多數 LCM 遞迴實作

public int LcmMultiple(params int[] numbers) {
    if (numbers.Length == 0) throw new ArgumentException("至少需要一個數字");
    if (numbers.Length == 1) return Math.Abs(numbers[0]);
    
    int result = Lcm(numbers[0], numbers[1]);
    for (int i = 2; i < numbers.Length; i++) {
        result = Lcm(result, numbers[i]);
    }
    return result;
}

// 範例：LCM(12, 9, 8) = LCM(LCM(12,9), 8) = LCM(36, 8) = 72

完整類別實作

public static class MathUtils {
    public static int Gcd(int a, int b) {
        a = Math.Abs(a); b = Math.Abs(b);
        while (b != 0) { int r = a % b; a = b; b = r; }
        return a;
    }
    
    public static int Lcm(int a, int b) {
        if (a == 0 || b == 0) return 0;
        return Math.Abs(a / Gcd(a, b) * b);
    }
    
    public static int Lcm(params int[] numbers) {
        if (numbers == null || numbers.Length == 0) return 0;
        int result = Math.Abs(numbers[0]);
        for (int i = 1; i < numbers.Length; i++) {
            result = Lcm(result, numbers[i]);
            if (result == 0) break; // 含 0 則 LCM 為 0
        }
        return result;
    }
}

應用場景

• 分數加減運算通分母
• 週期性事件同步週期計算
• 齒輪傳動比設計
• 排程系統最小共同週期

溢位防護建議

大數運算時建議使用 long 或 BigInteger：

using System.Numerics;
public static BigInteger Lcm(BigInteger a, BigInteger b) {
    if (a == 0 || b == 0) return 0;
    return BigInteger.Abs(a / Gcd(a, b) * b);
}