素数の和

Project Euler の Problem 10 は「200万以下の素数の和を求めよ」というものです。
Scheme で解くなら、昨日の記事に書いた prime-list が使えます。

(define problem-010
  (lambda (n)
    (printf "~d~%"
      (apply + (prime-list n)))))

> (time (problem-010 2000000))
142913828922
(time (problem-010 2000000))
    10 collections
    664 ms elapsed cpu time, including 167 ms collecting
    698 ms elapsed real time, including 173 ms collecting
    45340088 bytes allocated, including 45432536 bytes reclaimed

Chez Scheme はかなり高速だと思います。

私は Ruby も大好きです。Ruby で解くなら……

# problem_10.rb
def prime_list(n)
  return([]) if (n == 1)

  size = n / 2 - 1
  max  = Math::sqrt(n).to_i

  a = Array.new(size)
  size.times do |i|
    a[i] = 2 * i + 3
  end

  max.times do |i|
    j = a[i]
    next unless j
    ((j * j - 3) / 2).step(size, j) do |k|
      a[k] = nil
    end
  end

  return a.unshift(2).compact
end

sum = 0
prime_list(2000000).each do |i|
  sum = sum + i
end

puts sum

$ time ruby problem_10.rb
142913828922

real    0m4.512s
user    0m3.832s
sys    0m0.644s

4 秒ちょっとで解けました。まあ、Ruby に速度を求めているわけではないので、これで十分満足ですが……。