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.

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

hide comments
2015-08-12 12:42:43 LIveshell
Can anyone give me test cases...my submission shows WA...
2015-08-11 19:45:55 Carlos
Prime function doesn't return INT ? @jshade
2015-08-10 18:01:50
It always show time limit exceeded though it works on my system within the specified time limit

Last edit: 2015-08-10 18:02:32
2015-08-09 18:22:57
can anyone tell me how to reduce the time complexity? I used sieve of Eratosthenes but still it's exceeding time limit! here is my code. <snip>

Last edit: 2022-06-19 12:20:55
2015-08-07 11:40:38
I used the segmented sieve concept, but how to initialize an array of 1000000000 with true value ? It always gives RunTime error - Out of memory exception
2015-08-05 20:06:52 AbhiToChill
i keep geting runtime error (NZEC) but the code works perfectly on my system :/
am using python
2015-07-27 23:43:12
The trick to hitting the time limit is researching and knowing the theory behind finding Prime numbers. Begin with a brute force method, which is obviously going to be too slow, and reduce it from there. Read up on the facts of a prime number > including the fact that every prime >= 5 can be expressed as 6k+-1 . Good luck!

Last edit: 2015-07-27 23:43:58
2015-07-27 11:30:44 vivek keshore
For those who are struggling with Python. This problem is solvable using Python. I was able to get AC in 0.38 seconds using Python 2.7

Hint- Only Seg Sieve

Last edit: 2015-07-27 11:33:45
2015-07-25 21:01:51
i have tried to solve this prob a lot of times every time i get time limit so guys just move on i even learned some of c becuz of this :D
2015-07-25 19:13:47 Anurag Sharma
used ludacris theorem but failed to solve this.... looks easy but good ques. .... should be moved to tutorial...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.