sieve of eratosthenes

May 09, 2010

Update: Four months later, I found a bug in my code. if m < Math.sqrt(@number) should be if m <= Math.sqrt(@number)

Last week, I learned about Sieve of Eratosthenes. According to Wikipedia, it’s an ancient algorithm created by an ancient Greek mathematician, Eratosthenes, for finding all prime numbers (below 10 million).

I was asked to write the ancient algorithm in Ruby. Here is the code.

class Sieve
  attr_reader :prime_numbers
  
  def initialize(number)
    @number = number.to_i
    @prime_numbers = (2..@number).to_a
    remove_non_prime_numbers
  end

  def remove_non_prime_numbers
    @prime_numbers.each do |m|
      if m <= Math.sqrt(@number)
        @prime_numbers.each do |n|
          if m != n && n % m == 0
            @prime_numbers.delete(n)
          end
        end
      end
    end
  end
end

if $0 == __FILE__
  p = Sieve.new(ARGV[0]).prime_numbers
  puts 'There are ' + p.length.to_s + ' prime numbers: ' + p.join(', ')
end

sieve of eratosthenes

all posts