Sum of Euler's Totient Function

Euler's totient function phi(k) counts how many integers in the range [1, k] are coprime to k (share no common factor greater than 1 with k), with phi(1) defined as 1. Given an integer n, compute the sum phi(1) + phi(2) + ... + phi(n).

Input: A single line containing one integer n. Output: Print a single integer: the sum phi(1) + phi(2) + ... + phi(n).

1 <= n <= 2000000

This sieve-based technique for computing Euler's totient for EVERY number up to n simultaneously is a direct structural cousin of the Sieve of Eratosthenes - recognizing that many 'compute X for every number up to n' problems can be sieved together, rather than computed independently, is a powerful, reusable technique.

Compute the sum of Euler's totient function (counting numbers coprime to k) for every k from 1 to n, all at once. Brute force: Compute phi(k) individually for each k (by checking coprimality against every smaller number) and sum them - this costs O(n²) or worse, far too slow for n up to 2,000,000. Optimised: A SIEVE-BASED computation of ALL phi values at once (mirroring the Sieve of Eratosthenes' structure) computes every phi(k) for k from 1 to n in a single combined O(n log log n) pass, since each number's totient only needs adjusting once per DISTINCT PRIME factor it has - drastically faster than computing each phi(k) independently from scratch.

1. Compute phi(k) for EVERY k from 1 to n AT ONCE with a sieve: initialize phi[k]=k for all k. 2. This mirrors the Sieve of Eratosthenes: for i from 2 to n, if phi[i] is STILL equal to i, then i hasn't been touched yet and is PRIME - apply phi[j] -= phi[j]/i for every multiple j of i (including i itself). 3. After building the whole phi array in one sieve pass, sum phi[1..n] into a 64-bit accumulator.

Time: O(n log log n) - the same complexity class as the Sieve of Eratosthenes itself. Space: O(n), for the phi array covering every value from 1 to n.

n=1 gives a sum of exactly 1 (phi(1)=1 by convention). The sum grows roughly quadratically with n, so use a 64-bit accumulator even though n itself fits comfortably in a 32-bit int. n can be as large as 2,000,000, so an O(n log log n) sieve-based approach is required for performance.

Be ready to explain the sieve's core insight clearly: phi[i] still equaling i (untouched) is exactly how you detect that i is prime WITHOUT a separate primality check, since only prime factors ever trigger an adjustment.