Problem 7 - Project Euler

小さい方から数えて10001番目の素数．

素数表をgoogleで検索して適当にtext editorに貼り付け，スペースを改行に置換して10001行目を見ればいいと思います．

……なんて言ったら怒られそうなので．

# -vim- fileencoding: utf-8
#p(k) > k(lnk + lnlnk  ? 1)
import time
import math

st = time.time()
k = 10001
limit = int(k * (math.log(k) + math.log(math.log(k))))
flg = [True for i in range(3, limit + 1, 2)]
m = len(flg)
primes = [2]
for i in range(m):
    if flg[i]:
        primes.append(2 * i + 3)
        for j in range(3 * i + 3, m, 2 * i + 3):
            flg[j] = False
print(primes[k - 1], time.time() - st)

エラトステネスの篩を使った方が試し割よりも速いです．まぁ，10,000程度の個数なら平方根までの試し割でやってもそんなに時間かからないと思いますが．

limitはPierre Dusartが証明した個数と値の不等式から最大値付近を設定してるだけなので，そこら辺も適当でかまわないと思われます．