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 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.hide comments
|
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
|
|
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
<snip> <= please look at this and tell me why this doesn't work. :( Last edit: 2023-05-27 18:13:23 |
|
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 |
|
luisdanielmesa:
2015-07-19 23:53:09
I changed System.out.println(result) with a BufferedWriter and it got accepted... weird. |
| 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 |
RSS