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
|
silentguardian:
2015-08-17 18:12:08
What causes a SIGABRT error?I tried submitting a sieve of eratosthenes solution. |
|
pi_227:
2015-08-17 06:43:09
I don't have the problem of time complexity, but the compiler here gives wrong answer even though it works perfectly fine on my computer. |
|
Nurul Huda:
2015-08-16 19:06:33
Finally solved it after trying for couple of hours ! time 0.0 and memory 2.1 mb :D |
|
LIveshell:
2015-08-12 12:42:43
Can anyone give me test cases...my submission shows WA... |
|
Carlos:
2015-08-11 19:45:55
Prime function doesn't return INT ? @jshade |
|
vivked:
2015-08-10 18:01:50
It always show time limit exceeded though it works on my system within the specified time limit Last edit: 2015-08-10 18:02:32 |
|
prajal_5:
2015-08-09 18:22:57
can anyone tell me how to reduce the time complexity? I used sieve of Eratosthenes but still it's exceeding time limit! here is my code. <snip> Last edit: 2022-06-19 12:20:55 |
|
sarathsnair:
2015-08-07 11:40:38
I used the segmented sieve concept, but how to initialize an array of 1000000000 with true value ? It always gives RunTime error - Out of memory exception
|
|
AbhiToChill:
2015-08-05 20:06:52
i keep geting runtime error (NZEC) but the code works perfectly on my system :/
|
|
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 |
| 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