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!
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.
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.
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)
InformationAfter cluster change, please consider PRINT as a more challenging problem.
|Added by:||Adam Dzedzej|
|Cluster:||Cube (Intel Pentium G860 3GHz)|
|Languages:||All except: NODEJS PERL 6|
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
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
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
used ludacris theorem but failed to solve this.... looks easy but good ques. .... should be moved to tutorial...
CAN ANYONE PLEASE TELL ME WHERE TO GET THE SOLUTION CODE FOR THIS PROBLEM ,I AM UNABLE TO SOLVE IT
http://ideone.com/4ixSBo <= please look at this and tell me why this doesn't work. :(Last edit: 2015-07-23 19:45:55
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.
this one can be done by both segmented sieve and also direct primality test(have to optimize a little).
segmented sieve ;)
@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