(5)最小公倍數

能夠被某些數字都除盡的最小正整數稱為是這些數字的最小公倍數

【最後目標】

請找出數字1-20都能除盡的最小正整數

練習1：找出1,2,3,4,5,6,7,8,9,10都能除盡的最小正整數。

最直覺的方法，就是使用窮舉法，一個一個去測試是否滿足條件。

def find(value):
    for i in range(1, 11):
        if value % i > 0:
            return False
    return True

number = 11
while True:
    if find(number):
        break
    number = number + 1
print(number)

雖然可以用窮舉法來找答案，但是這個方法很沒有效率，尤其是隨著條件增加，要耗費更多時間。

要找出1-10都能除盡的最小正整數，用這個方法尚能接受。

但是如果是要找出1-20都能除盡的最小正整數，還是用這種暴力法來求解，並不是好方法。

因此，我們可以運用數學上的解法，先找出兩數的最大公因數，再進一步算出兩數的最小公倍數。

練習2:運用輾轉相除法求兩數最大公因數(GCD)

輾轉相除法是求最大公因數很有效率的方法，例如：我們求 a = 481 和 b = 221 的最大公因數。

(1)用大的數當被除數，小的數當除數，可得 481 = 2 * 221 + 39, 得到餘數39。

(2)再用小的數當被除數，餘數當除數，可得　221 = 5 * 39 + 26, 得到餘數26。

(3)重複第(2)步，直到餘數等於0，其除數就是最大公因數。

39 = 1 * 26 + 13, 26 = 2 * 13 + 0 因此 GCD(481, 221) = 13

數學上的輾轉相除法也很容易寫成程式碼用電腦去計算。

a = 481
b = 221
m = a % b
while (m > 0):
    a = b
    b = m
    m = a % b
print(b)

練習3：運用兩數乘積除以最大公因數求得最小公倍數

已知a、b兩數相乘等於其最大公因乘以最小公倍數，即 axb=(a,b)*[a,b]

那麼找出最大公因數後就可以拿來求最小公倍數。

def GCD(a, b):
    m = a % b
    while (m > 0):
        a = b
        b = m
        m = a % b
    return b

def LCM(a, b):
    return a * b // GCD(a, b)

print(LCM(481, 221))