Project Euler - Problem 10

もろもろの合間にちょっとした体操。

http://projecteuler.net/problem=10
200万までの素数の合計を求める。
単に素数リストを求めて合計すればいいだけ。

組み込みクラス使ってもいいけど、自前で実装する。

#!/usr/bin/env ruby

class Prime
  def list(max)
    # Eratosthenes
    list = (3..max).step(2).to_a
    result = [2]
    while(list.last > result.last ** 2) do
      result << list.shift
      list.reject! {|n| n % result.last == 0}
    end
    result + list
  end
end

# sum of primes
max = ARGV[0].to_i # 2000000
p Prime.new.list(max).reduce(&:+)

$ ruby -v
ruby 1.9.3p194 (2012-04-20 revision 35410) [x86_64-linux]

$ time ruby p10.rb 2000000
ruby p10.rb 2000000 469.85s user 1.62s system 99% cpu 7:53.67 total

reject の部分で素数の倍数を落としているが、件数が多すぎて時間がかかってしまう。
リストにして一気に落とした方が早いか。

#!/usr/bin/env ruby

class Prime
  def list(max)
    # Eratosthenes
    list = (3..max).step(2).to_a
    result = [2]
    while(list.last > result.last ** 2) do
      result << list.shift
      list -= (result.last..list.last).step(result.last).to_a
    end
    result + list
  end
end

# sum of primes
max = ARGV[0].to_i # 2000000
p Prime.new.list(max).reduce(&:+)

$ time ruby p10.rb 2000000
ruby p10.rb 2000000 12.65s user 0.23s system 99% cpu 12.914 total

arrayが演算できる言語だからできる手抜き。
Cでやると面倒そうだなあ。