1

I decided to code the sieve of eratosthenes in ruby for fun. Only for fun because I knew there was a library function. Also, I thought it would be fast. But I found that it is not, at least in my ruby 1.9.3, mine is several times faster on my netbook and it's not even in c. why is that so.

library implementation:

require 'prime'
primes = Prime.each(1_000_000).to_a
print primes.size
puts

mine in ruby:

sieve = Array.new(1_000_000, true)
sieve[0..1] = [false, false]
for number in 2...Math.sqrt(sieve.size)
  if sieve[number]
    for multiple in (number ** 2...sieve.size).step(number)
      sieve[multiple] = false
    end
  end
end

primes = []
for number in 2...1_000_000
  if sieve[number]
    primes << number
  end
end
print primes.size
puts

The library is very slow.

  • i think its time for me to upgrade to 2.2 –  Feb 04 '15 at 07:31
  • If you want to get still a little faster use a number wheel as discussed in http://stackoverflow.com/questions/17892313/sieve-of-eratosthenes-with-wheel-factorization. – Lutz Lehmann Feb 04 '15 at 13:30

2 Answers2

2

The prime library Prime.each(1_000_000).to_a generates all prime numbers below 1_000_000.

Your method actually only generate all prime number below the square root of 1_000_000, i.e, 1000.

Yu Hao
  • 119,891
  • 44
  • 235
  • 294
  • yes, thanks for catching that. i updated it. but still same problem –  Feb 04 '15 at 07:19
0

a) On my computer, library executes in 0.230s, your implementation in 0.270s on the average. EDIT: I executed on MRI 2.2.0 though, not 1.9.3.

b) More importantly, the library implementation for MRI is also in Ruby, not in C. Not all functions in Ruby library are written in native code.

Amadan
  • 191,408
  • 23
  • 240
  • 301