2.primeGenerator.py

from math import sqrt
primes = [2]
for i in xrange(3, 32000, 2):
	isPrime = True
	cap = sqrt(i) + 1
	for j in primes:
		if j >= cap:
			break
		if not i%j:
			isPrime = False
			break
	if isPrime:
		primes.append(i)
for _ in xrange(int(raw_input())):
	m, n = map(int, raw_input().split())
	isPrime = [True] * 100001
	if m is 1:
		m = 2
	cap = sqrt(n) + 1
	for i in primes:
		if i >= cap:
			break
		if i >= m:
			start = 2*i
		else:
			start = m + (i - m%i)%i
		isPrime[start - m: n + 1 - m: i] = [False] * len(isPrime[start - m: n + 1 - m: i])
	for i in xrange(m, n + 1):
		if isPrime[i - m]:
			print i
	print