# 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;
}
```