最大公因數

最大公因數（Greatest Common Divisor，GCD），也稱為最大公約數，是指兩個或更多個整數中最大的那個共同因子。一個數的因子是能夠整除該數的數字，例如，5的因子有1和5。

要找出兩個數字的最大公因數，你可以使用以下方法：

質因數分解法：將每個數字分解為質因數的乘積，然後找出共同的質因數，將它們相乘得到最大公因數。
試除法：用較小的數字試除較大的數字，記錄除得的餘數，然後用得到的餘數試除另一個數字，重複這個過程，直到兩個數字都能被某個數字整除為止，這個數字就是最大公因數。
歐幾里得算法（Euclidean algorithm）：這是計算兩個整數最大公因數的一種高效算法，其基本思想是：gcd(a, b) = gcd(b, a mod b)，其中a mod b表示a除以b的餘數。
質因數樹：將兩個數字分別畫成質因數樹，然後找出共同的質因數，將它們相乘得到最大公因數。

例如，要找出24和36的最大公因數，你可以使用質因數分解法：

24 = 2 × 2 × 2 × 3 36 = 2 × 2 × 3 × 3

共同的質因數是2 × 2 × 3，將它們相乘得到12，所以24和36的最大公因數是12。

或者使用試除法：

試除法： 24 ÷ 36 = 0餘24 36 ÷ 24 = 1餘12 24 ÷ 12 = 2餘0

所以24和36的最大公因數是12。