Lcm最大公因數計法

在數學中，「最大公因數」（Greatest Common Divisor，GCD）和「最低公倍數」（Least Common Multiple，LCM）是兩個相關的概念。

最大公因數（GCD）是指兩個或更多個數字中最大的共同因子。例如，對於數字12和18，它們的最大公因數是6，因為6是它們的共同因子中最大的。

最低公倍數（LCM）是指兩個或更多個數字中能夠被它們整除的最小正整數。例如，對於數字12和18，它們的最低公倍數是36，因為36是它們都能夠整除的最小正整數。

計算最大公因數和最低公倍數有幾種方法，以下是其中幾種常見的方法：

質因數分解法：將每個數字分解為質因數的乘積，然後找出所有共同的質因數，將它們相乘得到最大公因數。最低公倍數則是由所有質因數的乘積得到，然後將每個質因數的次數增加到最大公因數的次數上。
長除法：用較大的數字除以較小的數字，直到商為整數，然後將除數和餘數相加得到最大公因數。最低公倍數則是由除數和餘數相乘得到。
歐幾里得算法（Euclidean algorithm）：這是最常用的計算最大公因數的方法，它通過不斷地將較大的數字減去能夠整除較小數字的倍數，直到得到最大公因數。最低公倍數則是由最大公因數乘以兩數的乘積除以最大公因數得到的商。
質因數樹：將每個數字寫成質因數的乘積，然後找出所有共同的質因數，將它們相乘得到最大公因數。最低公倍數則是由所有質因數的乘積得到，然後將每個質因數的次數增加到最大公因數的次數上。

選擇哪種方法取決於數字的特徵和所需的精確度。例如，對於較小的數字，長除法可能更直觀，而對於較大的數字，質因數分解法或歐幾里得算法可能更有效。