Sphere Online Judge

SPOJ Problem Set (classical)

2. Prime Generator

Problem code: PRIME1


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)
Added by:Adam Dzedzej
Date:2004-05-01
Time limit:6s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All except: NODEJS PERL 6

hide comments
2014-04-21 19:01:55 Darshak Mehta
Can any one say me what should i print for m==n case
2014-04-11 16:56:39 Lincoln Lee
TLE T_T
2014-04-05 10:47:21 JOJO
How to remove run time error?
2014-04-05 04:14:59 Xavier
time limit exceed :(
2014-04-03 20:07:05 Mohan Bhambhani
My python code works perfectly on codechef and ideone but it shows time limit exceeded here...I am new to spoj please help me

Last edit: 2014-04-03 20:27:54
2014-03-31 07:06:24 Subrahmanya Venu Madhav Chitta
Such a good question it is...Wasted abt 3 hrs ... :(
2014-03-28 17:12:11 .::Lakshman::.
@Rahul Walkar RTE because of memory, read the problem statement once again, n can be up to 10^9 and you are allocating O(n) memory which is causing run time error you should learn about sieve, that might help.

Last edit: 2014-03-28 17:12:40
2014-03-24 06:11:25 mukthar ahamad
My code has run time error.how to rectify that.please help me.
2014-03-23 14:23:31 rodolfo
is there any special character i am missing ? every time i get WA, i have tryed pretty much any \n conbination, should i put \0 at the end or something ?
2014-03-17 09:23:54 Sourav Verma
every time time limit exceed :( :(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.