C# 最大公約數演算法：輾轉相除法標準實作

最大公約數 (GCD) 是能同時整除兩整數的最大整數。輾轉相除法（歐幾里得算法）為標準解法：反覆用較大數除以較小數取餘，直到餘數為 0，最後的除數即為 GCD。

標準實作

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

遞迴版本

public static int GcdRecursive(int a, int b) {
    a = Math.Abs(a);
    b = Math.Abs(b);
    return b == 0 ? a : GcdRecursive(b, a % b);
}

多數 GCD 擴展

public static int GcdMultiple(params int[] numbers) {
    if (numbers.Length == 0) throw new ArgumentException();
    int result = Math.Abs(numbers[0]);
    for (int i = 1; i < numbers.Length; i++) {
        result = Gcd(result, numbers[i]);
        if (result == 1) break; // 互質可提前結束
    }
    return result;
}

範例驗證

Gcd(24, 15) = 3
Gcd(100, 80) = 20
Gcd(17, 13) = 1  // 互質
GcdMultiple(60, 90, 150) = 30

效能特性

• 時間複雜度：O(log min(a,b))
• 最差情況：連續費波那契數（如 F(n+1), F(n)）
• 空間複雜度：迭代 O(1)、遞迴 O(log n)

.NET 內建替代方案

.NET Core 2.1+ / .NET Standard 2.1+ 提供 System.Numerics.BigInteger.GreatestCommonDivisor 支援大整數。