如何計算最大公因數

最大公因數（Greatest Common Divisor, GCD），也稱為最大公約數，是指兩個或更多個整數中最大的那個共同因子。計算最大公因數有幾種方法，這裡介紹幾種常見的方法：

1. 質因數分解法： 將兩個數分別分解為質因數的乘積，然後找出共同的質因數，將它們相乘得到最大公因數。

   例如，要找出 48 和 60 的最大公因數： 48 = 2^4 3 60 = 2^2 3 * 5 共同的質因數是 2^2 和 3，它們相乘得到 12，所以 48 和 60 的最大公因數是 12。

2. 長除法： 用較大的數除以較小的數，得到一個餘數。然後用除數除以這個餘數，再次得到一個餘數。重複這個過程，直到餘數為零，此時的除數就是最大公因數。

   例如，要找出 48 和 60 的最大公因數： 60 ÷ 48 = 1...12 48 ÷ 12 = 4 所以，48 和 60 的最大公因數是 12。

3. 歐幾里得算法（Euclidean algorithm）： 這是最常用的算法，可以用來計算兩個數的最大公因數。算法的原理是，如果 a > b，那麼 gcd(a, b) = gcd(b, a mod b)。

   假設我們要找出 a 和 b 的最大公因數，算法如下：

   1. 設 r = a % b
   2. 如果 r = 0，則 b 就是 a 和 b 的最大公因數
   3. 否則，重複步驟 1 使用 b 和 r

   例如，要找出 48 和 60 的最大公因數： 48 = 60 - 12 12 = 60 - 48 所以，48 和 60 的最大公因數是 12。

4. 質因數分解表： 如果數字已經被分解為質因數，可以使用質因數分解表來快速找出最大公因數。

   例如，要找出 12 和 18 的最大公因數： 12 = 2^2 3 18 = 2 3^2 最大公因數是 2 * 3 = 6。

這些方法中，歐幾里得算法是最常用的，因為它適用於任何整數，而且效率很高。在計算機科學中，通常使用快速算法如埃拉托斯特尼質因數分解算法來加速質因數分解的過程。