最小公因數算法

最小公因數（Greatest Common Divisor, GCD）是數論中的一個基本概念，它指的是兩個或更多整數的最大的共同正因子。在數學中，通常使用歐幾里得算法（Euclidean algorithm）來計算兩個整數的最小公因數。

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

1. 設兩個整數為 a 和 b，其中 a > b。
2. 計算 a 除以 b 的餘數，記作 r，即 a = b * q + r，其中 q 是整數，且 0 <= r < b。
3. 如果 r 為 0，則 b 就是 a 和 b 的最小公因數；否則，將 b 替換為 r，並重複步驟 2，直到 r 為 0 為止。

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

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

12 ÷ 8 = 1, 餘數 r = 4
將 b 替換為 r，現在 b = 4

8 ÷ 4 = 2, 餘數 r = 0
因為 r = 0，所以 b（現在是 4）就是 a 和 b 的最小公因數。

最小公因數 GCD(12, 8) = 4

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

在實際應用中，歐幾里得算法被廣泛用於數學、計算機科學、工程學等領域，尤其是在需要進行數字分解、質數檢測、模數運算等操作時。