最大公因數算法

最大公因數（Greatest Common Divisor, GCD）也稱為最大公約數，是指兩個或更多整數共有最大因數。在數學中，通常使用歐幾里得算法（Euclidean algorithm）來計算兩個整數的GCD。

歐幾里得算法的步驟如下：

1. 設兩個整數為 a 和 b，其中 a ≥ b。
2. 計算 a 除以 b 的餘數，記作 r，即 a = bq + r，其中 q 是整數，且 0 ≤ r < b。
3. 如果 r 為0，則 b 就是 a 和 b 的最大公因數；如果 r 不為0，則 a 和 b 的最大公因數等於 b 和 r 的最大公因數。
4. 重複步驟2和3，直到 r 為0為止。

以下是一個使用歐幾里得算法求兩個整數最大公因數的例子：

輸入兩個整數 a 和 b。
a = 12, b = 8

12 ÷ 8 = 1, 餘數 r = 4
最大公因數 GCD(12, 8) = GCD(8, 4)

8 ÷ 4 = 2, 餘數 r = 0
最大公因數 GCD(8, 4) = 4

所以，12 和 8 的最大公因數 GCD(12, 8) = 4。

歐幾里得算法不僅可以用來計算兩個整數的GCD，也可以用來計算多個整數的GCD。例如，要計算 a, b, c 的最大公因數，可以先計算 GCD(a, GCD(b, c))。