最大公約數相除法

最大公約數相除法（Greatest Common Divisor, GCD），又稱為歐幾里得算法（Euclidean algorithm），是計算兩個整數的最大公約數的一種算法。這個算法是由古希臘數學家歐幾里得在他的著作《幾何原本》中提出的，因此得名。

最大公約數相除法的原理是：兩個整數的最大公約數等於它們中的較小數與兩數相除的餘數的最大公約數。換句話說，如果我們有兩個數字a和b，我們可以通過以下步驟來找到它們的最大公約數：

1. 計算a除以b的餘數c（記為c = a mod b）。
2. 如果b == 0，則a是它們的最大公約數（GCD(a, b) = a），算法結束。
3. 否則，用b來代替a，用c來代替b，重複步驟1和2。

以下是一個簡單的Python例子，演示如何使用最大公約數相除法來找到兩個數字的最大公約數：

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# 示例
print(gcd(24, 18))  # 應該輸出6

這個算法的時間複雜度為O(log(max(a, b)))，因為它最多需要log(max(a, b))次除法。最大公約數相除法不僅可以用來計算兩個數字的最大公約數，還可以用來計算任意多個數字的最大公約數，只需要將算法適當擴展即可。