Chapter 125

Refactoring: Sieve for Totient

Computing φ(n) individually for each query costs O(√N). Computing all φ(1)..φ(N) at once with a sieve costs O(N log log N) — and gives you all of them.

Before: O(√N) per value

C++ — O(√N) each

for (int i = 1; i <= N; i++) result[i] = phi(i);  // O(N√N) — too slow!

After: O(N log log N) Sieve

C++ — totient sieve

vector phi_sieve(int n) {
    vector phi(n + 1);
    iota(phi.begin(), phi.end(), 0);

    for (int i = 2; i <= n; i++) {
        if (phi[i] == i) {  // i is prime
            for (int j = i; j <= n; j += i)
                phi[j] -= phi[j] / i;
        }
    }
    return phi;
}

// O(N log log N). phi[1..N] all computed.
// Uses the formula: for each prime p, multiply (p-1)/p into all multiples.