Primes in Interval (Million)

test1.py

from math import sqrt

#Sieve Of Eratosthenes - Start
last = int(sqrt(2147483647)) + 1
limit = int(sqrt(last)) + 1
arr = [True for i in range(0,last+1)]
i = 2

all_primes = []

while i <= limit:
	for im in range(i*i,last+1,i):
		arr[im] = False
	for j in range(i+1,last+1):
		if arr[j] == True:
			i = j
			break

for index in range(2,last+1):
	if arr[index]:
		all_primes.append(index)
#Sieve of Eratosthenes - End

t = int(input())
for testcase in range(0,t):
	m,n = input().split()
	m,n = int(m),int(n)
	answer = []

	#If small limit, we already have primes
	if n <= last:
		answer = [x for x in all_primes if x >= m and x <= n]
		for prime in answer:
			print(prime)

	#If large limit, we do segmented sieve
	else:
		
		if m < 2:
			m = 2
		
		#0 corresponds to m
		arr = [True for x in range(m,n+1)]
		primes = [x for x in all_primes if x <= int(sqrt(n))]
		for prime in primes:
			i = (m // prime) * prime
			if i == 0:
				i = i + (2*prime)
			elif i == prime:
				i = i + prime
			elif i < m:
				i = i + prime
			
			for im in range(i,n+1,prime):
				arr[im-m] = False

		for j in range(m,n+1):
			if arr[j-m] == True:
				print(j)