Rubyでエラトステネスの篩

３タイプのエラトステネスの篩を作ってベンチマークをとってみました

Type1

1. 2〜nの数値が入った配列を用意し、先頭から順に要素を取り出していく
2. 取り出した値を篩の配列に格納し、その値の倍数を配列から削除してしまう
3. nの平方根以上の値になったら、ループを停止
4. 配列に残った数値と、篩の配列を結合する

def test1(n)
  sqrtN = Math.sqrt(n).floor
  nums = (2..n).to_a
  flui = []
  while a = nums.shift
    flui << a
    break if sqrtN < a
    nums.delete_if { |b| b % a == 0 }
  end
  flui.concat(nums)
end

Type2

1. n+1個の長さを持つ配列を用意し、0と1をfalse、それ以外をtrueにする
2. 2〜sqrt(n)まで昇順に値を確認していき、trueなら篩配列に格納、それ以降の倍数を皆falseにしてしまう
3. ループが完了したら、配列でtrueになっているインデックス番号を追加で篩配列に入れる

def test2(n)
  sqrtN = Math.sqrt(n).floor
  dp = Array.new(n+1, true)
  dp.fill(false, 0, 2)
  flui = []
  2.upto(sqrtN) do |x|
    if dp[x]
      flui << x
      x.step(n+1, x) do |y|
        dp[y] = false
      end
    end
  end
  dp.each_with_index do |bool, idx|
    flui << idx if bool
  end
  flui
end

Type3

1. 0~nの要素を持つ配列を用意し、0と1をnilにする
2. sqrt(n)の値まで昇順に見ていき、もしnilでなければその値を除くその倍数を皆nilにする
3. 最後にnilだけを削除する

def test3(n)
  sqrtN = Math.sqrt(n).floor
  nums = (0..n).to_a
  nums.fill(nil, 0, 2)
  nums.each do |x|
    next if x.nil?
    break if sqrtN < x
    (x*2).step(n, x) do |y|
      nums[y] = nil
    end
  end
  nums.compact!
end

ベンチマーク

require 'benchmark'

Benchmark.bmbm 10 do |r|
  r.report "test1" do
    1000.times do |i|
      test1(1000)
    end
  end
  r.report "test2" do
    1000.times do |i|
      test2(1000)
    end
  end
  r.report "test3" do
    1000.times do |i|
      test3(1000)
    end
  end
end

• 結果

Rehearsal ----------------------------------------------
test1        0.280000   0.000000   0.280000 (  0.284107)
test2        0.180000   0.010000   0.190000 (  0.186512)
test3        0.140000   0.000000   0.140000 (  0.138681)
------------------------------------- total: 0.610000sec

                 user     system      total        real
test1        0.280000   0.010000   0.290000 (  0.282212)
test2        0.170000   0.000000   0.170000 (  0.180900)
test3        0.130000   0.000000   0.130000 (  0.138044)