PRIME1 - Prime Generator

no tags 

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 Pentium G860 3GHz)
Languages:All except: NODEJS PERL 6

hide comments
wesleyhovick: 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
vivek keshore: 2015-07-27 11:30:44

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
ahmed55: 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

Anurag Sharma: 2015-07-25 19:13:47

used ludacris theorem but failed to solve this.... looks easy but good ques. .... should be moved to tutorial...

philistine: 2015-07-25 00:15:37

CAN ANYONE PLEASE TELL ME WHERE TO GET THE SOLUTION CODE FOR THIS PROBLEM ,I AM UNABLE TO SOLVE IT

jshade: 2015-07-23 19:43:42

http://ideone.com/4ixSBo <= please look at this and tell me why this doesn't work. :(

Last edit: 2015-07-23 19:45:55
mrmighty: 2015-07-22 04:59:40

It is definitely doable in Python, although I got it to run in 4.2 seconds. Look at Miller-Rabin, as Sieve seems to be too inefficient. I also found that saving previously calculated primes was taking too long.

vasayashwanth: 2015-07-21 04:21:03

this one can be done by both segmented sieve and also direct primality test(have to optimize a little).

cosmopoliton: 2015-07-20 16:47:32

segmented sieve ;)

manureja: 2015-07-20 16:14:29

@minhquan: "time limit exceeded" means time taken by your code to get executed in the problem specific cpu of SPOJ is more than the maximum or desired time limit, as set by the person who gave the problem. In short, your code needs optimization.

Last edit: 2015-07-20 16:15:40