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 | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
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..
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. :)