Hcf最大公因數做法

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

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

   例如，求54和36的最大公因數： 54 = 2 × 3 × 3 × 3 36 = 2 × 2 × 3 × 3 最大公因數是 2 × 3 × 3 = 18

2. 長除法（Euclidean algorithm）： 這是最常用也是最有效的方法之一。基本思想是將第二個數除以第一個數，得到余數，然後將第一個數除以余數，得到新的余數，重複這個過程，直到余數為0，此時兩個數的商就是最大公因數。

   例如，求12和18的最大公因數： 18 ÷ 12 = 1...6 12 ÷ 6 = 2...0 所以，12和18的最大公因數是6。

3. 輾轉相除法（Extended Euclidean algorithm）： 這是一個更一般化的算法，不僅可以找到最大公因數，還可以找到兩個數的乘積除以最大公因數的餘數。

4. 更相減損法： 這是中國古代的一種算法，通過兩個數相減直到差為0來找到最大公因數。

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

6. 使用函數或工具： 在許多程式語言和軟件中，都有提供求最大公因數的函數或工具，可以直接使用。

選擇哪種方法取決於數的大小和具體情況。對於較小的數字，長除法通常就足夠了；對於較大的數字，可以使用更高效的算法。