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
p3arl_03: 2017-02-13 13:42:25

Hi guys,
I am getting time limit exceeded for my solution in java. But it is running fine on my ide.
Please suggest. Below is my solution-
[Do not post any source code here]

Last edit: 2017-02-14 10:35:10
varun98: 2017-02-12 18:51:56

is there any chat option on spoj platform ?

=(Francky)=> On top banner, you should see "Discuss" : that's a place. There's a link too, in notes, point 3, to the forum (same place).

Last edit: 2017-02-12 18:55:49
splashishkumar: 2017-02-11 23:17:27

simple friend..no use of any sieve....think simply...get AC more simply

premmuvva: 2017-02-09 20:51:04

bro if you get an error you try and try but don't go through any suggestions unless you are a beginner . it took me two days to do this code for which i was able to think about four totally new algorithms and new ways to percieve things hope you understand this

rohit9934: 2017-02-06 09:05:13

Time Limit Exceeded

Last edit: 2017-02-06 09:05:54
akash_23: 2017-02-05 15:01:53

good one! segmented sieve and AC!

shubham2305: 2017-02-05 10:13:22

didnt use seive or segmented seive
just a naive approach with some optimisation
thanks @sonudoo for suggesting such approach

ranjita: 2017-01-27 14:27:20

Rabin Miller is so nice

vietanisme: 2017-01-26 05:57:14

Get TLE for 3 - 4 times. Spend 30 mins to debug. Realized I was chosing the wrong version of C++. AC in one go

shubhama003: 2017-01-25 22:52:21

Segmented Sieve
AC in one go :)


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