最小公因數計法

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

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

1. 設兩個整數為 ( a ) 和 ( b )，其中 ( a > b )。
2. 計算 ( a ) 除以 ( b ) 的餘數，記作 ( r = a \mod b )。
3. 如果 ( r ) 不為 0，則將 ( b ) 替換為 ( r )，並重新執行步驟 2。
4. 當餘數為 0 時，( b ) 就是 ( a ) 和 ( b ) 的最小公因數。

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

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

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

12 ÷ 4 = 3, 餘數 r = 0
因為餘數為 0，所以最小公因數 GCD(12, 8) = 4。

除了歐幾里得算法，還有其他方法可以計算最小公因數，例如質因數分解法、輾轉相除法等。這些方法在不同的情況下可能有不同的效率，選擇適當的方法可以提高計算速度。