CODEWITHSUNDEEP
rubysieve-algorithm
jchi2241
jchi2241

Reputation: 2226

Improving efficiency of my Sieve of Eratosthenes in Ruby?

Below is my implementation of the Sieve of Eratosthenes to find prime numbers up to the upper limit parameter.

Currently, my code completes in around 2 seconds when my parameter is 2,000,000. I see that I'm making one extra step by setting the numbers to nil, and then compacting rather than just deleting those numbers in one step.

How would I go about implementing this? Do you also have any other suggestions to improve the speed of my code?

def sieve(upper)
  i = 0
  list = (2..upper).to_a

  (2..Math.sqrt(upper)).each do |mult|
    init = mult + i
    (init..upper-1).step(mult) do |index|
      list[index] = nil
    end
    i += 1
  end
  list.compact
end

Upvotes: 0

Views: 315

Answers (1)

Worakarn Isaratham
Worakarn Isaratham

Reputation: 1034

You could skip the loop where mult is not a prime number.

def sieve(upper)
  i = 0
  list = (2..upper).to_a
  (2..Math.sqrt(upper)).each do |mult|
    if list[i] #proceed only when mult is prime
      init = mult + i
      (init..upper-1).step(mult) do |index|
        list[index] = nil
      end
    end
    i += 1
  end
  list.compact
end

This trims down the runtime from 1.9 to 0.7 secs on my machine. I'm sure there's a lot more that can be done, though.

Upvotes: 1

Related Questions