SPOJ.com - Problem PRIME1

PRIME1 - Prime Generator

#number-theory

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

Input

The input begins with the number t of test cases in a single line (t ≤ 10). In each of the next t lines there are two numbers m and n (1 ≤ m ≤ n ≤ 1000000000, n-m ≤ 100000) separated by a space.

Output

For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

Example

Input:
2
1 10
3 5

Output:
2
3
5
7

3
5

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

Information

After cluster change, please consider PRINT as a more challenging problem.

Submit solution!

hide comments

< Previous 110 111 112 113 114 115 116 117 118 119 120 Next >

	VARUN KUMARE: 2013-03-13 22:12:29 Hey guys also try it!!! 1 1 2 4 3 5 1 10 999900000 1000000000
	roshin: 2013-03-13 22:12:29 the program works when i run[gcc] in my system. but here its showing compilation error.can anyone help me on this.......
	Chitirala Nagendra Vijay Kumar: 2013-03-13 22:12:29 can any one help me improving my approach.. thanQ.. <snip> Last edit: 2022-06-19 12:27:16
	capint: 2013-03-13 22:12:29 One of the error I encountered is forgetting the case when m = n. For people getting exceeded error, pay attention to the detail n-m<=100000.
	Believer: 2013-03-13 22:12:29 Can some one tell me what is wrong with this code?? <snip> Last edit: 2022-06-19 12:26:20
	Megha Ramesh Chandra Mantri: 2013-03-13 22:12:29 Hey, i am getting time exceeded error. But i am not able to get how to optimize it
	Rahul: 2013-03-13 22:12:29 I am getting SIGSEGV(runtime) error although it is running well on my machine. can anyone help me with this error?
	Jorian: 2013-03-13 22:12:29 plz, tell me what's wrong with my code <snip> Last edit: 2022-06-19 12:26:17
	edumandakh: 2013-03-13 22:12:29 nice solution
	Christian Scott: 2013-03-13 22:12:29 I've added input testing to make sure no weird tests are getting run and I've tested my output using (1,1), (3,5), (2,4) and loads of cases starting and ending on even numbers, prime numbers (including my last sifting prime), and of course I've run the obligatory (1000000000-100000,1000000000) and they all run perfectly and produce correct answers that I've verified using other prime number generators out there, but I still get WA. What could be the problem? Edit: In complete desperation I even tried manually adding \n and \r\n instead of letting Console.WriteLine() pick its own default. Still WA. Last edit: 2012-11-25 09:03:33

Submit solution!

Added by:	Adam Dzedzej
Date:	2004-05-01
Time limit:	6s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: NODEJS PERL6