PRIME1 - Prime Generator


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.

hide comments
मोहन: 2014-04-03 20:07:05

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
S Venu Madhav Chitta: 2014-03-31 07:06:24

Such a good question it is...Wasted abt 3 hrs ... :(

[Lakshman]: 2014-03-28 17:12:11

@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
mukthar ahamad: 2014-03-24 06:11:25

My code has run time error.how to rectify that.please help me.

rodolfo: 2014-03-23 14:23:31

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 ?

vermaz: 2014-03-17 09:23:54

every time time limit exceed :( :(

foxly: 2014-03-17 06:27:23

6 seconds is a reasonable time limit for languages like C, but makes the problem impossible for bytecode-interpreted languages like PHP. The time limit also needs to be set high enough or the ranges set low enough that its practical to brute-force it. This is problem #2 out of *thousands* ...you can't seriously be expecting people to be implementing advanced prime-finding algorithms on the second challenge after "hello world" ... :)

Sapan tanted: 2014-03-03 07:19:37

how to solve segmental error
i tried a lot bt not working

shaleen bakshi: 2014-02-18 17:42:09

i have been trying this problem for pretty long time and I am able to generate the answer which pretty much are correct . however when i try to upload the answer in here it shows me "wrong answer " . can anyone please help me with it !!

fernando: 2014-02-15 13:22:25

i have to hardcode the primes? because i have a nice algorithm and it exeed the time limit :(


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