この記事の所要時間： 約 1分10秒
No.10 Summation of primes
問題.
Q. 10 未満の素数の和は,
\begin{align*}
2+3+5+7 = 17
\end{align*}
です. では, 2,000,000 未満の素数の和はいくつになるか.
考え方とプログラム例(Python)
実際に 2,000,000 未満の素数を 「エラトステネスの篩」 を用いて求め, 和を求めていきます.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
import math N = 2000000 num = [0]*N num[0] = 1 for i in xrange(N): if num[i] == 0: if i+1 > math.sqrt(N): break n = 2*(i+1) while n <= N: num[n-1] = 1 n += (i+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 |
エラトステネスの篩の部分は,
自然数 \(i\) が素数 ⇔ \(num[i-1]=0\)
素数でない ⇔ \(num[i-1]=1\)
となるように実装しています.
配列 \(num[]\) にすべて 0 が入った状態から始めることで, エラトステネスの篩の最後の部分(\(\sqrt{2,000,000}\) を超えた時点で残っている数はすべて素数となる) を特に実装しなくて済みます.
最後に \(num[i-1]=0\) である \(i\) の和を求める部分は,
- filter を利用した方法(コメントアウトしてあります)
- list の内包表記を利用した方法
の2通りを書いてみました.
