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.