プロジェクトオイラー10.

この記事の所要時間: 110

No.10 Summation of primes

問題.

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

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

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

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

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

エラトステネスの篩の部分は,

自然数 \(i\) が素数 ⇔ \(num[i-1]=0\)

素数でない ⇔ \(num[i-1]=1\)

となるように実装しています.

配列 \(num[]\) にすべて 0 が入った状態から始めることで, エラトステネスの篩の最後の部分(\(\sqrt{2,000,000}\) を超えた時点で残っている数はすべて素数となる) を特に実装しなくて済みます.

最後に \(num[i-1]=0\) である \(i\) の和を求める部分は,

  1. filter を利用した方法(コメントアウトしてあります)
  2. list の内包表記を利用した方法

の2通りを書いてみました.

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加