Editorial

Why is this method of computing the Euler Totient Function incorrect? We assume that all numbers less than or equal to n are co-prime to n. Also, the GCD of (n, something) has to be a divisor of n. Since we will eventually iterate over all divisors of n, we can reduce the count of co-prime elements by 1 everytime we hit a divisor.

vector<int> compute_phi(int n) {
    vector<int> phi(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        // Assume all numbers are co-prime at first.
        // We will then reduce the count every time we see its divisor.
        phi[i] = i;
    }

    for (int i = 2; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            // j divides i, so reduce the divisor count by 1.
            phi[j]--;
        }
    }

    return phi;
}

Why is this method of computing the Euler Totient Function incorrect? We assume that all numbers less than or equal to n are co-prime to n. Note that a gcd is eventually a divisor, say d. If gcd is d, then gcd(n, number) = d implies that the gcd(n/d, number/d) = 1. Hence, all numbers that are co-prime to n/d can be extended to create an eventual gcd of d. Since there are phi(n/d) such numbers, we iterate over each divisor, and remove the contribution of phi(n/d).

vector<int> compute_phi(int n) {
    vector<int> phi(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        // Assume all numbers are co-prime at first.
        phi[i] = i;
    }

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

    return phi;
}