Problem 10

問題

Calculate the sum of all the primes below two million.

英語

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

Find the sum of all the primes below two million.

http://projecteuler.net/index.php?section=problems&id=10

日本語

10以下の素数の和は2 + 3 + 5 + 7 = 17である.
200万以下の全ての素数の和を計算しなさい.

注意: この問題は最近変更されました. 正しいパラメータを使用しているか確認してください。

http://odz.sakura.ne.jp/projecteuler/index.php?Problem%2010

解説

Primeクラスを使ってもいいけど速度が非常に遅いので
エラトステネスの篩で２百万以下の素数表を生成して総和。
ソースコード１の方は普通に実装したものだが高速。
ソースコード２の方は短くかけるけど非常に遅い。
だから１の方が便利

ソースコード1(Ruby)

prime = [2]  # 最初は 2 だけ
3.step(2e6, 2) do |i|
    add = true
    prime.each do |j|
        break if j**2 > i # sqrt(i) を超えれば抜ける

        if i % j == 0
            add = false 
            break
        end
    end
    prime << i if add
end
p prime.inject(:+)

ソースコード2(Ruby)

a = [*2..2e6]
b=[]
loop{
    b << a[0]
    a = a.delete_if {|x| x % b.max == 0}
    break if a.max < (b.max ** 2)
}
prime = (a + b).sort {|a, b| a<=>b}
p prime.inject(:+)