Finding number of primes till n - Sieve of Eratosthenes I've written a ruby implementation for Sieve of Eratosthenes algorithm, however benchmarking it against the Ruby's Prime module I have still a far slower algorithm - and I am struggling to understand why.

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 count_prime_till n
  primes_till(n).count
end

def multiples start,step_size,max
  (start...max).step(step_size)
end


Running it against,

puts Benchmark.measure { Prime::EratosthenesGenerator.new.first(1000).count }
  0.000000   0.000000   0.000000 (  0.000437)


Compared to mine,

puts Benchmark.measure {count_prime_till 7920}
  0.020000   0.000000   0.020000 (  0.025582)


Please let me know how can I improve the running time, and as always, readability.
You speed problem was caused by using the wrong data structure.  Since the sieve holds all the numbers up to n an Array is more efficient than a Set. 

As for style I removed your subroutines and added comments.  This will improve speed with little if any lose of readability.

def primes_till n
  possible_primes = Array.new(n+1)

  (2..n).each do |n|
    possible_primes[n] = n
  end

  # numbers with multiples less than n
  (2..(Math.sqrt(n)).ceil).each do |i|
    if possible_primes[i]
      # remove all multiples of the prime
      (i**2..n).step(i).each do |x|
        possible_primes[x] = nil
      end
    end
  end

  possible_primes.compact
end

require 'prime'
require 'benchmark'
s = 100000
x =  Prime::EratosthenesGenerator.new.first(s).last
raise unless Prime::EratosthenesGenerator.new.first(s).count == primes_till(x).to_a.count

puts Benchmark.measure { primes_till(x).count }
puts Benchmark.measure { Prime::EratosthenesGenerator.new.first(s).count }


This is slightly faster than the Prime::EratosthenesGenerator, but it does not knows that maximum size of the sieve and must do some extra work to handle that fact.