如何求最大公約數

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

試除法（Euclidean Algorithm）：這是最常用也是最有效的方法之一。基本思想是將第二個數字除以第一個數字，取餘數作為新的被除數，反覆進行直到餘數為0，此時商就是最大公約數。

例如，求50和15的最大公約數： 50 ÷ 15 = 3...10 15 ÷ 10 = 1...5 10 ÷ 5 = 2...0 因為餘數為0，所以最大公約數是5（即10除以5的結果）。
質因數分解法：將兩個數分別分解為質因數的乘積，然後找出共同的質因數，將它們相乘得到最大公約數。

例如，求24和36的最大公約數： 24 = 2^3 3^1 36 = 2^2 3^2 最大公約數是2^2 3^1 = 4 3 = 12。
使用函數或工具：在許多編程語言和計算器中，都有內置的函數可以直接計算最大公約數，例如在Python中可以使用math.gcd()函數。
```
import math
math.gcd(50, 15)  # 輸出: 5
```
長除法：將較大的數字除以較小的數字，記錄下每次除得的餘數，然後將這些餘數用短除法相除，直到得到兩個數字互質為止。最後一個除數就是最大公約數。

例如，求84和28的最大公約數： 84 ÷ 28 = 3...0 最大公約數是28（即84除以28的結果）。

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