プロジェクトオイラー10. ~ Summation of primes ~

No.10 Summation of primes

問題.

Q. 10 未満の素数の和は,

\begin{align*}
2+3+5+7 = 17
\end{align*}

です. では, 2,000,000 未満の素数の和はいくつになるか.

考え方とプログラム例(Python)

実際に 2,000,000 未満の素数を「エラトステネスの篩」を用いて求め, 和を求めていきます.

import math
N = 2000000
num = [0]*N
num[0] = 1
for i in range(N):
    if num[i] == 0:
        if i+1 > math.sqrt(N):
            break
        for n in range(2*(i+1), N+1, i+1):
            num[n-1] = 1
#Sum = sum(filter(lambda i : num[i-1] == 0, xrange(1, N+1)))
Sum = sum([i + 1 for i  in xrange(N) if num[i] == 0])
print(Sum)