Problem 10 - Project Euler

10以下の素数の和は2 + 3 + 5 + 7 = 17である.
200万以下の全ての素数の和を計算しなさい.

これもねぇ…素数のリストさえできれば簡単な問題ですよ。しかし僕の作ったコードでは素数リストの生成が終わる気配がありません。お手上げです。

終わらない計算

もうこれは解けそうに無いのでヒント探しの旅に出てみました。おかげ様でジェネレータの使い方が少しだけ身に付いた気がします。yieldいいね!yield!リスト内包についてもさらに理解が深まりました。しかし…ジェネレータを使って素数を出力するコードをいくつか試してみましたが、なんとどれも計算が終わりませんでした。すっかり途方に暮れてしまい「Pythonじゃ解けないんじゃ…」とか思い始める始末。

Pythonでは解けない!?

そんなことはないはずだと思いながらたまたま見つけたこの記事。


うさぎさんは(usagisanha)のBlog: Project Euler 9〜10

簡単簡単.


えええ!?まじですか!?


意を決してこの方のコードを拝借してみたところ…3秒くらいで終わった…

一体どうなっているのか

primeList = [True for i in xrange(max)]
#[True, True, True,....True]
primeList[0] = False
primeList[1] = False

おおお!いきなり要素が全部Trueのリスト作るのか!そして0番目と1番目の要素をそれぞれFalseに。

for i in xrange(2, len(primeList)):
    for j in xrange(2 * i, len(primeList), i):
        primeList[j] = False

外側のループで2〜len(primeList)まで回しつつ、内側のループで2*iの倍数になっている要素を次々とFalseに。

primeList = [i for i, v in enumerate(primeList) if v == True]

ここは仮に[i for i in enumerate(primeList)]とすると[(0, False), (1, False), (2, True), (3, True), (4, False)...]となります。[(i, v), (i, v)...]の形になっているので、つまりこれは「vがTrue(=素数)である要素のインデックスもまた素数」ということになるわけですね。


これがここまで高速なのは、途中まで扱うオブジェクトがTrueとFalseの2つだけだからなんでしょうねきっと。リストの中身が200万近くあったとしても、オブジェクトはTrueとFalseの2つだけなので驚くほど省メモリというわけですね。

今回は自分では解けませんでしたが、こういう発想もあるんだという発見があったこと、それを自分なりに分析してみたことで少しはレベルアップできたはず!