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.

5.sieve  # [2, 3, 5]
20.sieve # [2, 3, 5, 7, 11, 13, 17, 19]

Benchmarks

This benchmark loops through a handful of numbers 0 to 1 million in steps of 100000 and runs a sieve on each number.

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    41.430000   0.600000  42.030000 ( 42.261872)
Numeric#sieve    1.010000   0.250000   1.260000 (  1.342326)

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

                    user     system      total        real
sieve method    41.720000   0.730000  42.450000 ( 43.640117)
Numeric#sieve    0.960000   0.380000   1.340000 (  1.385924)

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    42.800000   0.910000  43.710000 ( 45.105879)
Numeric#sieve    1.090000   0.370000   1.460000 (  1.517832)

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

                    user     system      total        real
sieve method    22.800000   0.670000  23.470000 ( 24.132390)
Numeric#sieve    1.000000   0.380000   1.380000 (  1.422877)

Author

Written by Josh Clayton