C# 最大公約數（GCD）演算法：輾轉相除法實作

數學原理

最大公約數：能同時整除兩整數的最大整數。輾轉相除法（歐幾里得算法）：gcd(a,b) = gcd(b, a mod b)，直到餘數為 0，前一除數即為 GCD。例：gcd(24,15) → gcd(15,9) → gcd(9,6) → gcd(6,3) → gcd(3,0) = 3。

C# 實作

public 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;
}

原始碼分析與改進

原文件使用 float 回傳、Math.Max/Min 交換、三元運算確保 a≥b，實際上：

• GCD 必為整數，int/long 即可，避免浮點誤差。
• 模運算 a % b 隱含 a≥b 邏輯（a 時 a%b=a，下一輪自動交換），無需額外比較。
• 處理負數：取絕對值或直接用模運算特性（C# 餘數符號同被除數，GCD 定義域為自然數，建議先 Abs）。

// 多數 GCD
public int Gcd(params int[] nums)
{
    int g = nums[0];
    for (int i = 1; i < nums.Length; i++)
        g = Gcd(g, nums[i]);
    return g;
}

// LCM = a*b / GCD(a,b)  （注意溢位，可用 long 或 BigInteger）
public long Lcm(long a, long b) = Math.Abs(a * b) / Gcd((int)a, (int)b);