最小公倍數怎麼求

求兩個或更多數字的最低公倍數（Greatest Common Divisor, GCD）有幾種方法，其中最常用的是質因數分解法和歐幾里得算法（Euclidean algorithm）。

質因數分解法： 首先將每個數字分解為質因數的乘積，然後找出所有共同的質因數，最後將這些質因數相乘得到最低公倍數。

例如，要找出24和36的最低公倍數，我們先將它們分解為質因數： 24 = 2^3 3^1 36 = 2^2 3^2

它們共同的質因數是2和3，將這些質因數相乘得到最低公倍數： 2^3 3^2 = 8 9 = 72

所以，24和36的最低公倍數是72。

歐幾里得算法（適用於兩個數的情況）： 歐幾里得算法是一種遞歸算法，用於找出兩個整數a和b的最大公約數。它的基本思想是不斷用b除以a的餘數來代替a，直到a和b相等為止。此時，a就是a和b的最大公約數。

算法步驟如下：

1. 如果b == 0，則a和b的最大公約數是a；
2. 如果b != 0，則找出a % b的餘數c；
3. 用b替換a，用c替換b，並返回步驟2。

以下是一個使用歐幾里得算法求最低公倍數的例子：

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def lcm(a, b):
    g = gcd(a, b)
    return a * b // g

a = int(input("第一個數："))
b = int(input("第二個數："))
print("最低公倍數：", lcm(a, b))

在這個例子中，gcd 函式是歐幾里得算法，用於找出兩個數的最大公約數。lcm 函式使用 gcd 函式來計算最低公倍數，a * b // g 表示 a 和 b 的乘積除以它們的最大公約數。

運行這個程式，輸入兩個數，就可以得到它們的最低公倍數。