1353. Add Up Every Totient
Print the sum of the totients of every integer from 1 to n, where the
totient of k counts how many values from 1 to k are coprime to k.
n = 5 -> 1 + 1 + 2 + 2 + 4 = 10
Calling problem 1319 once per value costs O(n sqrt(n)), which is far too slow
at n = 10^6.
Compute them all at once with a sieve. Start every entry at its own index, then
for each prime p, apply the factor 1 - 1/p to every multiple of p:
phi[i] = i for all i
for i from 2 to n:
if phi[i] == i: i is prime, untouched so far
for j = i, 2i, 3i, ... up to n:
phi[j] -= phi[j] / i
The test phi[i] == i identifies primes for free: any composite has already been
reduced by one of its factors, so only a prime still equals its index when the
outer loop reaches it.
Note the inner loop starts at i, not i*i, because here i itself must also be
reduced. That is the opposite of problem 1352 and mixing them up is easy.
The total reaches about 3 * 10^11 at the maximum, so accumulate in 64 bits even
though each individual entry fits comfortably in 32.
Constraints - `1 ≤ n ≤ 1000000`
Input
One line containing the integer n.
Output
Print the sum of the totients of 1 through n.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.