[解決済み] Project Euler 5 in Python - どうすれば解を最適化できますか？

質問内容

最近、PythonでProject Eulerの問題に取り組んでいます。私はPythonにかなり慣れておらず、プログラマーとしてもまだ少し経験が浅いです。

いずれにせよ、問題番号5の解答をコーディングする際に、スピードに関する問題にぶつかった。その問題とは

2520は、1から10までの数字で余すことなく割り切れる最小の数字である。1から20までのすべての数で均等に割り切れる最小の正の数は何ですか?"

いくつか調べてみましたが、特にPythonに関連するこの問題についてのものは見つかりませんでした。完成したスクリプトもありましたが、できれば他の人のコードを丸ごと見るのは避けて、自分のコードを改善したいのです。

私が書いたコードは、2520の例と1から10の範囲で正常に実行され、質問で動作するように直接修正することができるはずです。しかし、それを実行すると、私は答えを得ることはできません。おそらく、非常に大きな数字であり、コードの速度が十分でないのでしょう。現在チェックされている数を印刷すると、これを裏付けているようで、数百万に達しても答えが得られません。

現在の実装では、以下のようなコードになっています。

rangemax = 20
def div_check(n):
    for i in xrange(11,rangemax+1):
        if n % i == 0:
            continue
        else:
            return False
    return True

if __name__ == '__main__':
   num = 2
   while not div_check(num):
       print num
       num += 2
   print num

私はすでに、スピードアップに役立つと思われる変更をいくつか加えています。1つ目は、ある数字が1から20までのすべての数字で割り切れるためには、偶数でなければなりません。(これは調べていませんが、理にかなっていると思います。）

しかし、このコードではまだ十分な速度が得られません。このコードをより速く実行するために、プログラム的または数学的にどのような最適化が可能でしょうか？

お分かりになる方、よろしくお願いします。

解決方法は？

Michael Miorさんやpokeさんのアドバイスを受けて、解決策を書きました。 高速化するためにちょっとした工夫をしてみました。

比較的短い数字のリストをテストする必要があるので、それなら、繰り返し xrange() または range() .

また、単に数字を並べるだけではうまくいきませんが [1, 2, 3, ..., 20] をリストに入れれば、少し考えて、数字を抜き出すことができます。

1を取り出せばいいんだよ。 すべての整数は1によって均等に割り切れる。

20を残すなら、2を残す必要はない。 20で割り切れる整数はすべて2で割り切れる（ただし、逆は真でない場合がある）。 そこで、20を残し、2と4と5を取り除く。 この作業を繰り返すと、試すべき数字のリストがずっと少なくなる。

Michael Miorが提案したように、20から始めて、20ずつ数を増やしていきます。 の内部でジェネレーター式を使用します。 all() というのは、ポークが提案したとおりです。

の代わりに while ループを使用し for ループに xrange() この方が若干速いと思います。

その結果

check_list = [11, 13, 14, 16, 17, 18, 19, 20]

def find_solution(step):
    for num in xrange(step, 999999999, step):
        if all(num % n == 0 for n in check_list):
            return num
    return None

if __name__ == '__main__':
    solution = find_solution(20)
    if solution is None:
        print "No answer found"
    else:
        print "found an answer:", solution

私のパソコンでは、9秒以内に答えが見つかります。

EDIT David Zaslavskyのアドバイスに従えば、2520からループを始めて、2520ずつステップを踏んでいけばいいことがわかります。 そうすると、私のコンピュータでは、約10分の1秒で正しい答えが得られます。

を作りました。 find_solution() は引数を取ります。 を呼び出してみてください。 find_solution(2520) .