Hcf最大公倍數計法
求兩個或更多整數的「最大公因數」（Greatest Common Divisor, GCD）和「最低公倍數」（Least Common Multiple, LCM）是數學中常見的問題，有許多方法可以解決這些問題。以下是一些常用的方法：
最大公因數（GCD）計算方法：
-
質因數分解法：將每個數分解成質因數的乘積，然後找出所有共同的質因數，將它們相乘得到GCD。
-
長除法：使用長除法將較大的數除以較小的數，直到兩數相等，最後的餘數就是GCD。
-
歐幾里得算法（Euclidean algorithm）：這是計算GCD的一種高效算法，其基本思想是不斷用較大的數字減去較小數字的倍數，直到兩個數字相等。
最低公倍數（LCM）計算方法：
-
質因數分解法：將每個數的質因數找出，然後將所有質因數的最高次方相乘，得到的數就是LCM。
-
乘法法：將所有數相乘，然後除以GCD，得到的數就是LCM。
-
分數表達法：將每個數寫成分數形式，分子為1，分母為GCD，然後將這些分數相乘，得到的分數的分子就是LCM，分母為GCD。
這裡有一個簡單的例子來解釋這些方法：
假設我們要找出數字12和18的GCD和LCM。
最大公因數（GCD）：
- 質因數分解法：12 = 2^2 3^1, 18 = 2^1 3^2，所以GCD(12, 18) = 2^1 * 3^1 = 6。
- 長除法：18 ÷ 12 = 1...6，12 ÷ 6 = 2，所以GCD(12, 18) = 6。
- 歐幾里得算法：18 - 12 = 6，12 - 6 = 6，所以GCD(12, 18) = 6。
最低公倍數（LCM）：
- 質因數分解法：LCM(12, 18) = 2^2 * 3^2 = 36。
- 乘法法：LCM(12, 18) = 12 * 18 / 6 = 36。
- 分數表達法：LCM(12, 18) = 1/1 1/6 1/1 * 1/2 = 36 / 6 = 36。
所以，12和18的GCD是6，LCM是36。