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
```