Project euler Ploblem 7 (プロジェクトオイラー7)
備忘のために残しておく。
コードを修正しました(指摘ありがとうございます)
問題
問題文 (意訳)
素数をはじめから順に6個並べると、2,3,5,7,11,13。6番目の素数は13だとわかる。
10001番目の素数は?
原文
By listing the first six prime numbers: 2, 3, 5, 7, 11 and 13 , we can see that the 6th prime is 13 .
What is the 10001st prime number?
解答
答え
104743
解答の方針
エラトステネスのふるいを使って10001個より大きい素数のリストを作成し、10001番目の素数をリストから取り出す。
Pythonのコード
Python Ploblem7
def eratosthenes(n: int) -> list:
"""エラトステネスのふるい"""
isprime = [True] * (n+1)
isprime[0], isprime[1] = False, False
# ふるい
for p in range(2, n + 1):
素数以外(False)を飛ばす
if not isprime[p]:
continue
# p 以外の p の倍数をふるいにかける(TrueをFalseに)
q = p + p
while q <= n:
isprime[q] = False
q += p
l = [x for x in range(n+1) if isprime[x]]
return l
def seek_ans(limit: int, interval: int = 100000) -> int:
# intervalは適当な値を置いている
n = 2
while len(eratosthenes(n)) < limit:
n += interval
return eratosthenes(n)[limit-1]
print(seek_ans(10001))
Juliaのコード
Julia Ploblem7
function eratosthenes(n::Int64)::Vector{Int64}
# エラトステネスのふるい
isprime = fill(true, n+1)
isprime[1] = false
for p in 2:n
if !isprime[p]
continue
end
# p 以外の p の倍数をふるいにかける(TrueをFalseに)
q = p + p
while q <= n
isprime[q] = false
q += p
end
end
l = [x for x in 1:n if isprime[x]]
return l
end
function seek_ans(limit::Int64, interval::Int64 = 100000)::Int64
# intervalは適当に置く
n = 2
while length(eratosthenes(n)) < limit
n += interval
end
return eratosthenes(n)[limit]
end
println(seek_ans(10001))
コメント
@WolfMoon
1
@WolfMoon1
@fujitanozomu(藤田 望)
該当部分有効化
該当部分無効化
1
@fujihop1
は,やめるべし。意味ない。
エラトステネスの篩の実装例は多いが,
https://qiita.com/WolfMoon/items/0483ac130684a10cf25e
なども見てください。
@fujihopさん、
は有効にした方が無駄な処理が省けるので良いと思いますがどうして無効化されるんですか?
で比較してみました。
処理に掛かった時間を秒で出力しています。有効化した場合に比べて無効化した場合では 3倍近く処理時間が掛かっています。
@fujitanozomu さん コメント・検証ありがとうございます。
「ふるい」としては正しく、有効なものですね。
いいね以上の気持ちはコメントで