1365. Add Up the Primes
Print the sum of every prime from 2 up to and including n. With n < 2 the
sum is 0.
10 -> 2 + 3 + 5 + 7 = 17
100 -> 1060
Testing each value with trial division is O(n sqrt(n)), which is slow at
n = 10^6. A sieve of Eratosthenes finds every prime in O(n log log n), which
is effectively linear, and then the sum is one pass.
The sieve itself is four lines, and the two efficiency details are both worth knowing:
the outer loop only needs to reach sqrt(n)
the inner loop can start at p*p rather than 2p
Both follow from the same fact. Any composite below p*p has a factor smaller
than p and was already struck out, so starting earlier repeats work that is
finished.
The answer overflows a 32-bit integer easily: the primes below 10^6 sum to
about 3.75 * 10^10. The sieve entries are bytes and the total is 64-bit, and
mixing those up is the mistake to avoid.
Constraints - `1 ≤ n ≤ 1000000`
Input
One line containing the integer n.
Output
Print the sum of all primes from 2 to n inclusive, or 0 if there are none.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.