« Project Euler --- 素数を扱う問題 | トップページ | Turtle Graphics on Ruby/SDL ver.2.0 »

2008年12月16日 (火)

素数の和

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 に速度を求めているわけではないので、これで十分満足ですが……。

« Project Euler --- 素数を扱う問題 | トップページ | Turtle Graphics on Ruby/SDL ver.2.0 »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

Scheme」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/43433658

この記事へのトラックバック一覧です: 素数の和:

« Project Euler --- 素数を扱う問題 | トップページ | Turtle Graphics on Ruby/SDL ver.2.0 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ