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
|
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. |
|
|
luisdanielmesa:
2015-07-19 23:31:31
I'm getting wrong answer although the code runs fine against a pre-computed list... |
|
mzy115:
2015-07-13 12:54:41
easy |
| 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