I'v tried to solve this problem from 4 or 5 days, but the only solution that I'v wrote finish running in 84 seconds using Segmented Sieve.
So is there any hints or resources to start working on the correct solution?
I'v tried to solve this problem from 4 or 5 days, but the only solution that I'v wrote finish running in 84 seconds using Segmented Sieve.
So is there any hints or resources to start working on the correct solution?
# | User | Rating |
---|---|---|
1 | ecnerwala | 3649 |
2 | Benq | 3581 |
3 | orzdevinwang | 3570 |
4 | Geothermal | 3569 |
4 | cnnfls_csy | 3569 |
6 | tourist | 3565 |
7 | maroonrk | 3531 |
8 | Radewoosh | 3521 |
9 | Um_nik | 3482 |
10 | jiangly | 3468 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 162 |
4 | TheScrasse | 159 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 151 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
Name |
---|
You don't actually need to find all primes to cimpute the sum. E.g.here is a description of an approach, that only takes O(n^0.75) time. Link
Thank you for the link, but can you explain the method used? because I don't understand it.
What exactly didn't you understand? The only method used here is DP.
They just define a function that does a bit more than just a summation of the primes. S(v, p) is the sum of all numbers between 2 and v which are still in the sieve if you remove all multiples of all primes ≤ p. Every non-prime number below n has a factor , so the answer to the problem is .
And for this function it is not too hard to come up with a recursive definition. If you don't understand it, just try it with a few numbers. E.g. for S(25, 3), and see what numbers they sum up, and what numbers you sum up with S(25, 3), and which numbers with 3 * S(8, 2) and 3 * S(2, 2).
Implementation was not described in the link. But I assume that a top-down DP approach is fast enough.