I have been trying to solve a problem on segmented sieve i.e prime1(http://www.spoj.com/problems/PRIME1/) in spoj but i am getting wrong answer and unable to find the bug in the code. So please help me..
I have been trying to solve a problem on segmented sieve i.e prime1(http://www.spoj.com/problems/PRIME1/) in spoj but i am getting wrong answer and unable to find the bug in the code. So please help me..
# | User | Rating |
---|---|---|
1 | tourist | 3690 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 166 |
3 | adamant | 163 |
4 | TheScrasse | 160 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
Name |
---|
Sieve Of Eratosthenes will give TLE. It works only for numbers <= 10^6, maybe <= 10^7 with complexity O(n*ln(ln(n))). While checking if number is prime works with numbers <= 10^12 with complexity O(sqrt(n)).
If there are 10 test cases, with worst case of n — m = 100000
worst complexity will be 100000 * 10 * sqrt(1000000000). it would surely tle
reply to sbakic
This will give TLE too. You're doing 105 * log109 operations, which is over 3000M operations.
The correct solution is to generate a list of prime numbers beforehand, and then mark non-prime numbers in the range [A, B] (if a number is not prime, then there is a prime less or equal than its square root that divides it).
Here's the code: C++ Code with comments
UPDATE: Your solution was OK, albeit slower because it uses map instead of unordered_map. You only needed to consider that l is not prime if l divides p and l > p. Your program didn't consider this last condition and didn't print 2 when l = 2.
I think this problem should be solved using segmented sieve algorithm. :)