Rubyでサブプライム問題解決！ 〜Rubyでオイラープロジェクトを解こう！Problem10

Problem 10 - Project Eulerより

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
10未満の素数の和は、2 + 3 + 5 + 7 = 17 である。
200万未満の素数すべての和を求めよ。

Problem3で既に素数を求めているので
それを使って解く
200万はちょっと大きいので
まずは2万を入れて…

 def sum_prime(limit)
   sum = 0
   prime = 2
   loop do
     break if prime > limit
     sum += prime if prime?(prime)
     prime += 1
   end
   sum
 end

 def prime?(n)
   2.upto(n-1) do |i|
     return false if n.modulo(i).zero?
   end
   true
 end

 t = Time.now
 sum_prime(20_000) # =>21171191
 Time.now - t # => 73.649596

ぎゃ！
2万で73秒…
200万だと…

じゃあ…
エラトステネスのふるいでやってみよう

エラトステネスの篩 - Wikipediaより

ステップ 1
　整数を最初の素数である 2 から昇順で探索リストに羅列する。
　2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
ステップ 2
　リストの先頭の数を素数リストに記録する。
　素数リスト：2
　探索リスト：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
ステップ 3
　前のステップで素数リストに加えられた数の全ての倍数を、探索リストから削除する。
　素数リスト：2
　探索リスト：3 5 7 9 11 13 15 17 19
ステップ 4
　探索リストの最大値が素数リストの最大値の平方よりも小さい場合、素数リストおよび探索リストに残っている数が素数となる。探索リストの最大値が素数リストの最大値の平方よりも大きい場合、ステップ 2 に戻る。

各ステップをそのままコードにしてみた

 def sum_prime(limit)
   candidates = (2..limit).to_a
   primes = []
   loop do
     primes << candidates.shift
     candidates.delete_if do |i|
       primes.any? { |e| (i % e).zero? }
     end
     return (primes + candidates).inject(:+) if candidates.max < (primes.max ** 2)
   end
 end

 t = Time.now
 sum_prime(20_000) # => 21171191
 Time.now - t # => 6.052391

6秒に短縮された
でも200万を入れると…
…
…
答えが出てこない！

あきらめるか…

と…
mathnライブラリに
Primeクラス発見！
これ使っちゃお

 require "mathn"

 def sum_prime(limit)
   sum = 0
   Prime.each do |prime|
     return sum if prime > limit
     sum += prime
   end
 end

 t = Time.now
 sum_prime(2_000_000) # => 142913828922
 Time.now - t # => 26.524741

これで
サブムプライム問題
無事解決！