Primes in a range

primes.rb

class BitSet
  def initialize
    @bm = {}
  end
  def set(i)
    n = i >> 4
    @bm[n] = @bm[n].to_i | (1 << (i & 0xF))
  end
  def test(i)
    @bm[i/16].to_i[i & 0xF] != 0
  end
end
def sieve(n_from, n_to)
  h = BitSet.new

  n1 = (n_from - 1) / 2
  n1 = 1 if n1 < 1
  n2 = (n_to + 1) / 2

  up = (n2 - 1) / 3
  from = ((Math.sqrt(1 + 2 * n1) - 1) / 2).floor
  from = 1 if from < 1
  from.upto(up) do |i|
    l = (n1 - i) / (2*i + 1)
    l = 1 if l < 1
    u = (n2 - i) / (2*i + 1)
    u = i if u > i
    puts "#{l} #{u} #{i} #{up}"  if i % 100000 == 0
    l.upto(u) do |j|
      k = i + j + 2*i*j
      break if k > n2
      next if k < n1
      h.set(k)
    end
  end
  n_from |= 1
  (n_from..n_to).step(2).select{|k| !h.test((k-1)/2)}
end
#p sieve(0, 10000)
p sieve(2**30 - 1000, 2**30)