Sieve of Eratosthenes

A Ruby gem for easy sieving

Install

Install with Rubygems:

gem install sieve

Usage

A method is added to the Numeric class.

>> require "sieve"
=> true
>> 5.sieve
=> [2, 3, 5]
>> 100.sieve
=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Benchmarks

This benchmark loops through a handful of numbers 0 to 1 million in steps of 100000 and runs a sieve on each number. I also include benchmarks for running the sieve against 10 million and 100 million.

The sieve method itself looks like this:

def sieve(n)
  numbers = (0..n).map
  numbers[0] = numbers[1] = nil
  numbers.each do |num|
    next unless num
    break if num**2 > n
    (num**2).step(n, num) {|idx| numbers[idx] = nil }
  end
  numbers.compact
end

As far as I know, this is the most optimized pure Ruby sieve written.

The benchmarks were run on a 2.8GHz Intel Core 2 Duo MacBook Pro with 8 GB memory.

ruby 1.8.6 (2010-02-05 patchlevel 399) [i686-darwin10.4.0]

                        user     system      total        real
sieve method        4.450000   0.060000   4.510000 (  4.526172)
Numeric#sieve       0.040000   0.000000   0.040000 (  0.046676)
sieve 10_000_000    8.780000   0.120000   8.900000 (  9.010072)
10_000_000.sieve    0.080000   0.000000   0.080000 (  0.084518)
100_000_000.sieve   2.050000   0.050000   2.100000 (  2.128403)

ruby 1.8.7 (2010-08-16 patchlevel 302) [i686-darwin10.4.0]

                        user     system      total        real
sieve method        4.460000   0.060000   4.520000 (  4.522069)
Numeric#sieve       0.040000   0.000000   0.040000 (  0.046349)
sieve 10_000_000    8.820000   0.120000   8.940000 (  8.955888)
10_000_000.sieve    0.080000   0.010000   0.090000 (  0.083030)
100_000_000.sieve   2.040000   0.040000   2.080000 (  2.100103)

ruby 1.8.7 (2010-04-19 patchlevel 253) [i686-darwin10.4.0], MBARI 0x6770, Ruby Enterprise Edition 2010.02

                        user     system      total        real
sieve method        4.610000   0.090000   4.700000 (  4.730966)
Numeric#sieve       0.050000   0.010000   0.060000 (  0.046442)
sieve 10_000_000    8.640000   0.060000   8.700000 (  8.731662)
10_000_000.sieve    0.100000   0.000000   0.100000 (  0.104731)
100_000_000.sieve   2.250000   0.050000   2.300000 (  2.303147)

ruby 1.9.2p0 (2010-08-18 revision 29036) [x86_64-darwin10.4.0]

                        user     system      total        real
sieve method        2.410000   0.060000   2.470000 (  2.468430)
Numeric#sieve       0.050000   0.000000   0.050000 (  0.049053)
sieve 10_000_000    4.770000   0.110000   4.880000 (  4.888397)
10_000_000.sieve    0.080000   0.000000   0.080000 (  0.098229)
100_000_000.sieve   2.090000   0.040000   2.130000 (  2.137024)

Author

Written by Josh Clayton

License

See the LICENSE