prime1.rb

# SPOJ - PRIME1 http://www.spoj.com/problems/PRIME1/
#
# *NOTE*
#
# 1. Presieve the primes under sqrt(1_000_000_000).
# 2. Multiple the primes to flag numbers which are not primes.
# 3. Sieve in given range.

primes = [2]

3.step(32000, 2) do |num|
  next if primes.any?{|p| num % p == 0}
  primes << num
end

line_count = gets.to_i
while line_count > 0
  line_count -= 1

  a,b = gets.split.map(&:to_i)
  a = 2 if a < 2

  not_prime = {}

  primes.each do |prime|
    break if prime*prime > b

    if prime >= a
      start = 2*prime
    else
      start = a + (prime - a % prime) % prime
    end

    while start <= b
      not_prime[start] = true unless not_prime[start]
      start += prime
    end
  end

  a.upto(b).each{|num| puts num unless not_prime[num] }

  puts unless line_count == 0
end