如何計算最大公約數

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

試除法（Euclidean Algorithm）：這是最常用也是最有效的方法之一。基本思想是將較大的數字除以較小的數字，取餘數作為新的被除數，重複這個過程直到兩個數互質（即只有公因數1）。最後，將過程中得到的除數作為最大公約數。

例如，要找出12和18的最大公約數，我們可以這樣做： 18 ÷ 12 = 1 R 6 12 ÷ 6 = 2 6 ÷ 2 = 3 因為2和3互質，所以最大公約數是2。
質因數分解法：將兩個數分別分解成質因數的乘積，然後找出共同的質因數，將它們的次方取最小值，相乘得到最大公約數。

例如，要找出48和60的最大公約數，我們可以將它們分解質因數： 48 = 2^4 3 60 = 2^2 3 5 共同的質因數是2^2和3，所以最大公約數是2^2 3 = 12。
使用函數或工具：在許多程式語言和軟件中，都有內置的函數或工具可以直接計算最大公約數。例如，在Python中可以使用math.gcd()函數來計算最大公約數。
```
import math
math.gcd(48, 60)  # 輸出: 12
```
長除法：這是一種簡單但效率較低的方法。將較小的數字作為除數，較大的數字作為被除數，進行長除，直到被除數除以除數沒有餘數為止。最後，將除數作為最大公約數。

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

選擇哪種方法取決於數字的大小和可用的資源。對於較小的數字，試除法或長除法可能就足夠了；對於較大的數字，質因數分解法可能更有效；而在編程中，使用內置函數或工具是最方便快捷的方法。