• 數學解題程式設計：使用Python 3

最小公倍數

• 講義
• 影片

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

  【最後目標】

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

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

    

  • 運用輾轉相除法求兩數最大公因數(GCD)

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

    要找出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、b兩數相乘等於其最大公因乘以最小公倍數，即 axb=(a,b)*[a,b]

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