素数の和

Project Euler 10

$10$ 以下の素数の和は、$2+3+5+7=17$ である。
$2000000$ 以下の素数の和を計算せよ。

---

まずは力づくでやってみた。

素数を格納するためのリストを生成し、$2000000$ までの数（以下、$x$）を順番に素数リスト内の数で割ってみる。
余りなく割ることができれば合成数と判定し、どの素数でも割り切ることができなければ、$x$ を素数として素数リストへ追加する。
なお、計算時間を低減するため、素数リストの値が $\sqrt{x}$ を超えた場合、該当の数を素数と判定する。

# SAMPLE_1

from math import sqrt


N = 2000000
prime_list = [2]
x = 3
s = 2

while (x <= N):
    for j in prime_list:
        if j > int(sqrt(x)) + 1:
            prime_list.append(x)
            s += x
            break
        if x % j == 0:
            break
    else:
        prime_list.append(x)
        s += x
    x += 2
print s

次にエラトステネスの篩を使ってみた。
素数リストとして、$x$ 番目が $1$ の場合は素数、$0$ の場合は合成数となるものを作成する。

まず、素数リストをすべて $1$ で初期化する。
次に $2$ から順番に、当該数の倍数の素数リストを $0$ にしていく。この際、対象数が既に合成数と判定されている場合は無視する。

# SAMPLE_2

N = 2000000

l = [1 for _ in range(N+1)]
l[0] = l[1] = 0

s = 0
for x in range(2, N+1):
    if l[x] == 0:
        continue
    s += x
    for j in range(2*x, N+1, x):
        l[j] = 0
print s

実際にやってみると、圧倒的に後者のほうが処理時間が短い。