Sieve of Eratosthenes

In working on Project Euler's 'Largest prime factor' problem I wanted a better way to find primes in a range than brute force testing each number. After a little research I found the  "Sieve of Eratosthenes". (What a great name.)

The idea is, instead of iterating through each number in a range and testing if it's prime; when you find a prime, remove all of it's multiples from the range, then continue iterating. So in the 1-100 example, finding 2 lets you get rid of 49 possibilities (all the evens except for 2) and finding 3 lets you eliminate 32 more. So almost right away you've gone from iterating through 100 possibilities to 19.

It's one of the most efficient ways to find prime numbers up to about 10,000,000 according to Wikipedia and a couple other sources I found.

Ruby's Prime class has an Eratosthenes Generator which you can use to, well, generate prime numbers of course.

irb > require 'Prime'
irb > prime_generator = Prime::EratosthenesGenerator.new
=> #<Prime::EratosthenesGenerator:0x000001011aaa20 @last_prime_index=-1, @ubound=nil>
irb > primes = []
irb > 10.times do
irb >   primes << prime_generator.next
irb > end
=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Because I want to better understand ol' Eratosthenes and I need a range of primes between x and y, I wrote my own method.

require 'prime'

def eratosthenes_sieve(num)
  raise "#{num} is too big a number for eratosthenes_sieve. Please enter a number under 10000000." if num > 9999999
  raise "2 is the first prime number. Please enter a number of 2 or greater." if num < 2
  range = (2..num).to_a
  range.each do |number|
    if number.prime?
      # puts "#{number} is prime"
      range.each_with_index do |p, i|
        if p % number == 0 && p > number 
          range.delete_at(i) 
          # puts "Deleting #{p}"
        end
      end
    end
  end
  range
end

A couple notes:

  • This includes a raise in case someone tries to use it with too big a number. Above that number the sieve isn't as efficient and the process would run for a long time taking up a lot of memory.
  • With a large number it can take a while so there are 2 puts statements that can be commented out to watch it work.

I think it could be more efficient so I'm going to work on improving it in the next couple weeks. Having a prime generator seems pretty handy!