問題

問題文 (意訳)

10より下の素数の和は　2 + 3 + 5 + 7 = 17。
2,000,000より下の全ての素数の和を求めよ。

原文

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

解答

答え

142913828922

解答の方針

エラトステネスのふるいを使って素数のリストを作成し、合計する。
[Python][Julia]Project euler7 (プロジェクトオイラー7)
のコードを参考に改変した。

Pythonのコード

Pyhton ploblem10

def prime_sum(n: int) -> int:
    """エラトステネスのふるいを使い、素数をリストアップして足す"""
    isprime = [True] * (n + 1)
    isprime[0], isprime[1] = False, False
    # ふるい
    for p in range(2, n + 1):
        # 素数以外(False)を飛ばす
        if isprime[p]:
            # 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 sum(l)

prime_sum(2000000)

Juliaのコード

Julia Ploblem10

function prime_sum(n::Int64)::Int64
    isprime = trues(n)
    isprime[1] = false
    for p in 2:n
        if isprime[p]
            q = p + p
            while q <= n
                isprime[q] = false
                q += p
            end
        end
    end
    l = [x for x in 1:n if isprime[x]]
    return sum(l)
end

println(prime_sum(2000000))