[Python][Julia]Project euler7 (プロジェクトオイラー7)

Project euler Ploblem 7 (プロジェクトオイラー7)

10001st Prime

備忘のために残しておく。
コードを修正しました(指摘ありがとうございます)

問題

問題文 (意訳)

素数をはじめから順に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(l := eratosthenes(n)) < limit:
        n += interval
    return l[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))

追記

セイウチ演算子(:=)についての参考記事
セイウチ演算子って何？