No.7 10001st prime
問題.
考え方とプログラム例(Python)
1. 小さい数から順に素数かどうかを確かめていく
素数の定義通りに, 自分よりも小さい数で割り切れないものを順に素数と判定していくことを考えます.
はじめにリスト prime =[2] としておき, prime に含まれるすべての数で割り切れない最小の数を素数としてこのリストに追加していきます.
リストサイズが10001になったところで計算を終了します.
prime = [2] i = 3 while len(prime) < 10001: f = 0 for p in prime: if i % p == 0: f = 1 break if f == 0: prime.append(i) i += 1 print(prime[10000])
この方法では, 素数で割り切れるかの確認を何回も行う必要がありすこし時間がかかってしまいます.
2. 素数定理から上限を設定し, エラトステネスの篩(ふるい)を用いる
素数の判定に, エラトステネスの篩を使うことを考えます.エラトステネスの篩では, あらかじめ調べる上限の設定が必要です.
(つまり, 1,000,000以下の素数をすべて求めるときの1,000,000 のような)
そこで, 上限を用意するために, 素数定理を使います.
\begin{align*}
10001 < \dfrac{n}{\ln(n)}
\end{align*}
を満たす最小のをエラトステネスの篩における上限として設定します.
import math N = 30 L = 0 while L < 10001: N += 1 L = N/math.log(N) num = [0]*N num[0] = 1 prime = [] for i in range(N): if num[i] == 0: prime.append(i+1) n = 2*(i+1) while n <= N: num[n-1] = 1 n += (i+1) if i + 1 > math.sqrt(N): for (j, k) in enumerate(num[i:]): if k == 0: prime.append(j+i+1) break print prime[10000]
こちらの方法では, 1. の方法よりも早く計算できました.