最大公因數計法

最大公因數（Greatest Common Divisor, GCD），也稱為最大公約數，是指兩個或更多整數共有因數中的最大一個。計算最大公因數有許多方法，以下是一些常見的方法：

1. 試除法（Euclidean Algorithm）： 這是最常用的方法，它通過不斷將較大的數減去較小的數，直到得到兩個數互質（沒有除了1以外的公因數）為止。最後，將得到的差作為較小數的因數來回推，找到最大公因數。

   例如，要找出12和18的最大公因數，我們可以這樣做： 18 - 12 = 6 12 - 6 = 6 因為12和6已經互質，所以6是它們的最大公因數。

2. 質因數分解法： 將每個數分解成質因數的乘積，然後找出所有共同的質因數，將它們相乘得到最大公因數。

   例如，要找出24和36的最大公因數，我們可以這樣做： 24 = 2^3 3^1 36 = 2^2 3^2 最大公因數是2^2 * 3^1 = 12。

3. 質因數樹： 質因數樹是一種圖形化的方法，用來找出數字的質因數，並從中找出最大公因數。

   例如，要找出18和24的最大公因數，我們可以這樣做：

   • 畫出18和24的質因數樹。
   • 找出兩個數共同的質因數，即2和3。
   • 將這些質因數相乘得到最大公因數，即2 * 3 = 6。

4. 長除法： 將較小的數作為除數，較大的數作為被除數，進行長除，直到被除數除以除數沒有餘數為止。最後的商就是最大公因數。

   例如，要找出12和18的最大公因數，我們可以這樣做： 18 ÷ 12 = 1...6 12 ÷ 6 = 2 因為12和6已經互質，所以6是它們的最大公因數。

這些方法都可以用來計算兩個或更多整數的最大公因數。選擇哪種方法通常取決於數字的性質和問題的要求。