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

この記事の所要時間: 144

No.7 10001st prime

問題.

Q. はじめの6つの素数は 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 です.

では, 10001番目の素数は何か.

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

1. 小さい数から順に素数かどうかを確かめていく

素数の定義通りに, 自分よりも小さい数で割り切れないものを順に素数と判定していくことを考えます.

はじめにリスト prime =[2] としておき, prime に含まれるすべての数で割り切れない最小の数を素数としてこのリストに追加していきます.

リストサイズが10001になったところで計算を終了します.

この方法では, 素数で割り切れるかの確認を何回も行う必要があり, 計算時間は \(6.68\)秒かかりました.

2. 素数定理から上限を設定し, エラトステネスの篩(ふるい)を用いる

素数の判定に, エラトステネスの篩を使うことを考えます.

エラトステネスの篩では, あらかじめ調べる上限の設定が必要です.

(つまり, 1,000,000以下の素数をすべて求めるときの1,000,000 のような)

そこで, 上限を用意するために, 素数定理を使います.

自然数 \(n\) 以下の素数の数 \(\pi(n)\) は\(\dfrac{n}{\ln(n)}\) で近似され,

\begin{align*}
10001 < \dfrac{n}{\ln(n)}
\end{align*}

を満たす最小の\(n\)をエラトステネスの篩における上限として設定します.

こちらの方法では, 0.124秒で答えが求まりました.

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