Ram wants to generate some prime numbers for his cryptosystem. Help him please!
Your task is to generate all prime numbers between two given numbers.

Warning: large Input/Output data, be careful with certain languages (though most should be OK if the algorithm is well designed)

------ Input Format ------ 

The first line contains t, the number of test cases (less then or equal to 10). 

Followed by t lines which contain two numbers m and n (1 ≤ m ≤ n ≤ 1000000000, n-m≤100000) separated by a space.

------ Output Format ------ 

For every test case print all prime numbers p such that m ≤ p ≤ n,
one number per line.  Separate the answers for each test case by an empty line.

------ Constraints ------ 

(1 ≤ m ≤ n ≤ 1000000000, n-m≤100000)

----- Sample Input 1 ------ 
2
1 10
3 5
----- Sample Output 1 ------ 
2
3
5
7

3
5

Source: codechef | Difficulty: EASY
Tags: Number theory

Mathematics


Solutions:
def isprime(n):
	if num < 2:
		return False
	elif n == 2 or n == 3:
		return True
	elif n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, int(n ** 0.5) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True
for _ in range(int(input())):
	(m, n) = map(int, input().split())
	for num in range(m, n + 1):
		if isprime(num):
			print(num)


t = int(input())

def isprime(n):
	if n < 2:
		return False
	if n == 2 or n == 3:
		return True
	if n % 2 == 0 or n % 3 == 0 or n % 4 == 0:
		return False
	for i in range(5, int(n ** 0.5) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True
for i in range(t):
	(a, b) = map(int, input().split())
	if a <= 2:
		print(2)
	if a % 2 == 0:
		a += 1
	for k in range(a, b + 1, 2):
		if isprime(k):
			print(k)
	print()


def isPrime(n):
	if n < 2:
		return False
	elif n == 2 or n == 3:
		return True
	elif n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, int(n ** 0.5) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True
t = int(input())
for _ in range(t):
	(l, u) = map(int, input().split())
	for i in range(l, u + 1):
		if isPrime(i):
			print(i)


import math

def isPrime(n):
	if n < 2:
		return False
	if n == 2 or n == 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	m = int(math.sqrt(n))
	for i in range(5, m + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True
t = int(input())
while t:
	(m, n) = map(int, input().split())
	for i in range(m, n + 1):
		if isPrime(i):
			print(i)
	t -= 1


def prime(k):
	if k <= 1:
		return 0
	elif k == 2:
		return 1
	elif k % 2 == 0:
		return 0
	else:
		for i in range(3, int(k ** 0.5) + 1, 2):
			if k % i == 0:
				return 0
		return 1
t = int(input())
for a in range(t):
	(n, m) = map(int, input().split())
	for i in range(n, m + 1):
		if prime(i):
			print(i)
	print()


def isprime(j):
	if j < 2:
		return False
	elif j == 2 or j == 3:
		return True
	elif j % 2 == 0 or j % 3 == 0:
		return False
	for i in range(5, int(j ** 0.5) + 1, 6):
		if j % i == 0 or j % (i + 2) == 0:
			return False
	return True
t = int(input())
for tc in range(t):
	(l, u) = map(int, input().split())
	for j in range(l, u + 1):
		if isprime(j):
			print(j)


def prime(n):
	if n < 2:
		return False
	elif n == 2 or n == 3:
		return True
	elif n % 2 == 0 or n % 3 == 0 or n % 4 == 0:
		return False
	for i in range(5, int(n ** 0.5) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True
for i in range(int(input())):
	(m, n) = map(int, input().split())
	for i in range(m, n + 1):
		if prime(i):
			print(i)
	print()


def isprime(n):
	if n < 2:
		return False
	elif n == 2 or n == 3:
		return True
	elif n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, int(n ** 0.5) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	for t in range(x, y + 1):
		if isprime(t):
			print(t)


import math

def prime(n):
	l = math.floor(math.sqrt(n))
	if n == 1:
		return False
	if n == 2 or n == 3 or n == 5:
		return True
	if n % 2 == 0 or n % 3 == 0 or n % 5 == 0:
		return False
	for i in range(3, l + 1, 2):
		if n % i == 0:
			return False
	return True
for _ in range(int(input())):
	(m, n) = map(int, input().split(' '))
	for i in range(m, n + 1):
		if prime(i):
			print(i)


import math

def check(n):
	if n == 1:
		return False
	if n == 2:
		return True
	elif n % 2 == 0:
		return False
	else:
		for k in range(3, int(math.sqrt(n)) + 1, 2):
			if n % k == 0:
				return False
	return True

def prime(x, y):
	for j in range(x, y + 1):
		if check(j) == True:
			print(j)
t = int(input())
for i in range(0, t):
	(x, y) = map(int, input().split())
	prime(x, y)


def prig(n):
	if n < 2:
		return False
	elif n == 2 or n == 3:
		return True
	elif n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, int(n ** 0.5) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True
n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	for i in range(a, b + 1):
		if prig(i):
			print(i)


def prime(n):
	if n <= 1:
		return False
	elif n == 2 or n == 3:
		return True
	elif n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, int(n ** 0.5) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True
for i in range(int(input())):
	(x, y) = map(int, input().split())
	for j in range(x, y + 1):
		if prime(j):
			print(j)


def isPrime(n):
	if n < 2:
		return False
	elif n == 2 or n == 3:
		return True
	elif n % 2 == 0 or n % 3 == 0 or n % 4 == 0:
		return False
	for i in range(5, int(n ** 0.5) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True
cases = int(input())
for i in range(cases):
	(x, y) = map(int, input().split())
	for i in range(x, y + 1):
		if isPrime(i):
			print(i)


import math

def prime(a):
	if a == 2:
		return True
	elif a % 2 == 0:
		return False
	elif a > 1:
		for i in range(3, int(math.sqrt(a)) + 1, 2):
			if a % i == 0:
				return 0
		return 1
for _ in range(int(input())):
	a = [int(x) for x in input().split()]
	for j in range(a[0], a[1] + 1):
		if prime(j) == 1:
			print(j)


import math

def prime(a):
	if a == 2:
		return True
	elif a % 2 == 0:
		return False
	elif a > 1:
		for i in range(3, math.isqrt(a) + 1, 2):
			if a % i == 0:
				return False
		return True
t = int(input())
for i in range(t):
	(m, n) = map(int, input().split())
	for i in range(m, n + 1):
		if prime(i):
			print(i)


def checkPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	c = 5
	while c * c <= n:
		if n % c == 0 or n % (c + 2) == 0:
			return False
		c += 6
	return True
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	for i in range(a, b + 1):
		if checkPrime(i):
			print(i)


import math

def prime(i):
	if i == 2 or i == 3:
		return 1
	elif i > 3:
		if i % 2 == 0 or i % 3 == 0:
			return 0
		for j in range(3, int(math.sqrt(i)) + 1, 2):
			if i % j == 0:
				return 0
		else:
			return 1
for _ in range(int(input())):
	(a, b) = map(int, input().strip().split())
	for k in range(a, b + 1):
		if prime(k) == 1:
			print(k)


import math

def prime(b):
	if b <= 1:
		return False
	elif b == 2 or b == 3:
		return True
	elif b % 2 == 0 or b % 3 == 0:
		return False
	for i in range(5, math.ceil(b ** 0.5) + 1, 6):
		if b % i == 0 or b % (i + 2) == 0:
			return False
	return True
T = int(input())
for _ in range(T):
	(a, b) = map(int, input().split())
	for i in range(a, b + 1):
		if prime(i):
			print(i)