回上方
登入

最小公倍數

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

【最後目標】

請找出數字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))


本單元課程自2018.2.21日起已被瀏覽 6060