It seems I've followed pretty much both the optimization and the algorithm given in the link... Not sure what more can I do.

```
require 'set'
def numbers_with_multiples_less_than n
(2...(Math.sqrt(n)).ceil)
end
def primes_till n
possible_primes = Set.new(2...n)
(numbers_with_multiples_less_than n).each do |i|
if possible_primes.include? i
possible_primes = possible_primes - Set.new(multiples i**2,i,n)
end
end
possible_primes
end
def multiples start,step_size,max
(start...max).step(step_size)
end
# @param {Integer} n
# @return {Integer}
def count_primes(n)
primes_till(n).count
end
```