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

この記事の所要時間: 123

No.10 Summation of primes

問題.

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

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

です. では, 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通りを書いてみました.

答えはこの下の行にあります. 反転してください.

A. 142913828922

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