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, nm<=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 5Warning: 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:  20040501 
Time limit:  6s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel Pentium G860 3GHz) 
Languages:  All except: NODEJS PERL 6 
hide comments
wesleyhovick:
20150727 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: 20150727 23:43:58 

vivek keshore:
20150727 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


ahmed55:
20150725 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:
20150725 19:13:47
used ludacris theorem but failed to solve this.... looks easy but good ques. .... should be moved to tutorial... 

philistine:
20150725 00:15:37
CAN ANYONE PLEASE TELL ME WHERE TO GET THE SOLUTION CODE FOR THIS PROBLEM ,I AM UNABLE TO SOLVE IT


jshade:
20150723 19:43:42
http://ideone.com/4ixSBo <= please look at this and tell me why this doesn't work. :( Last edit: 20150723 19:45:55 

mrmighty:
20150722 04:59:40
It is definitely doable in Python, although I got it to run in 4.2 seconds. Look at MillerRabin, as Sieve seems to be too inefficient. I also found that saving previously calculated primes was taking too long. 

vasayashwanth:
20150721 04:21:03
this one can be done by both segmented sieve and also direct primality test(have to optimize a little). 

cosmopoliton:
20150720 16:47:32
segmented sieve ;) 

manureja:
20150720 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: 20150720 16:15:40 