数学の力

京大生が数学の定理・公式の証明や入試問題の解説をするブログ.

プロジェクトオイラー7. ~ 10001st prime ~


スポンサードリンク

No.7 10001st prime

問題.

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

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

 

考え方とプログラム例(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 のような)

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


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

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

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

 

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. の方法よりも早く計算できました.