Finding number of primes till n - Sieve of Eratosthenes
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.