pythonで最小公倍数を求めるプログラムの速度を上げる方法を教えてください。

Question

前提・実現したいこと

タイトル通りです。
また、初心者のためおすすめの変数名やこうした方がいいなどのテクニックなど教えていただけたら大変大変ありがたいです。

'''
Problem 5 「最小の倍数」 †
2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.

では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.
'''

該当のソースコード

import sys

count = 11
current = 20

while True:
    for i in range(1, current+1):
        if count%i :
            break
    else :
        print( count )
        sys.exit()
    count += 1

Answer 1

20×19×9 (18/2) ×…
を計算していくのが早そうです。
つまり、
20, 19,18…と見ていくのですが、
最初は20
→次は19 (19は今まで出てきた数の約数で割り切れない)
→次は9 (18は20の約数2で割り切れる)
→次は17(17は今まで出てきた数の約数で割り切れない)
→…

Answer 2

結論をいうとこれでできます。(Python >= 3.5)
Python3.4の場合はgcd(最大公約数)モジュールはmathではなくfractionにあるので注意です。

import math

ans = 1
for i in range(2, 21):
    ans = ans * i // math.gcd(ans, i)
print(ans)

まず、ans * i // math.gcd(ans, i)はansとiで割り切れる数、すなわち最小公倍数を計算します。
1と2の最小公倍数を求め、その数と3の最小公倍数を求め、さらにその数と4の...とやっているうちに、1から20までの最小公倍数をもとめることができます。

Comments

[fukatani]

最大公約数はユークリッドの互除法というアルゴリズムで求めると高速ですが、Pythonならgcd関数を叩けば内部でやってくれます。

[malia]

ありがとうございます
一瞬で計算が終わりました
数学的な理由がわかりませんが大体の動きはわかりました。
あとは調べてみます。