エラトステネスの篩２

昨日に続いてエラトステネスの篩の話

昨日見つけたソースコードを見てるとどうしてもパフォーマンスが気になったので測定してみた。

require 'benchmark'

Benchmark.bm do |x|
    x.report("My Primes:") {
        prime = [2]  # 最初は 2 だけ
        3.step(1e6, 2) do |i|
            add = true
            prime.each do |j|
                break if j**2 > i # sqrt(i) を超えれば抜ける

                if i % j == 0
                    add = false
                    break
                end
            end

            prime << i if add
        end
    }

    x.report("Ruby Primes:"){
        a = [*2..1e6]
        b=[]
        loop{
            b << a[0]
            a = a.delete_if {|x| x % b.max == 0}
            break if a.max < (b.max ** 2)
        }
        prime = (a + b).sort {|a, b| a<=>b}
    }
end

      user     system      total        real
My Primes:     17.470000   0.050000     17.520000 ( 17.592847)
Ruby Primes:   324.560000  1.060000     325.620000 (327.121505)

速度を見たらやっぱり前に使ってたほうが圧倒的に早かった。
short codingするなら後者を使うかもしれないけど、
大規模の素数表を作るなら前者の方を使おう。