Introduction

Euler’s totient function phi(n) counts how many integers from 1 to n are coprime with n. Efficient implementations do not test every number individually; instead, they factor n and use the fact that each distinct prime factor removes a predictable fraction of candidates.

The key formula behind the implementation

If the distinct prime factors of n are p1, p2, and so on, then:

phi(n) = n * (1 - 1/p1) * (1 - 1/p2) * ...

That formula is the reason efficient implementations work. You do not need to compute greatest common divisors for every integer up to n. You only need the distinct prime factors.

For example, if n = 12, the distinct prime factors are 2 and 3. Then:

• start with 12
• remove the fraction divisible by 2
• remove the fraction divisible by 3

The result is 4, corresponding to 1, 5, 7, and 11.

Efficient implementation by prime factorization

A standard implementation checks divisors up to the square root of n. Whenever it finds a prime factor, it removes that factor completely and adjusts the result once.

1def phi(n: int) -> int:
2    result = n
3    p = 2
4
5    while p * p <= n:
6        if n % p == 0:
7            while n % p == 0:
8                n //= p
9            result -= result // p
10        p += 1
11
12    if n > 1:
13        result -= result // n
14
15    return result
16
17
18for value in [1, 2, 9, 12, 36]:
19    print(value, phi(value))

This implementation is efficient because each prime factor affects the result only once, no matter how many times that prime divides n.

Why the loop works

The loop does two jobs:

1. find a prime factor p
2. divide n by p until that factor is fully removed

The line:

result -= result // p

implements the formula step for one distinct prime factor. It removes the numbers that are not coprime because they share that factor.

After the loop finishes, if n > 1, then the remaining n itself is a prime factor larger than the square root of the original number. That last prime still needs to be applied to the result once.

Example walk-through for n = 36

Start with:

• 'n = 36'
• 'result = 36'

The first factor found is 2.

• divide out all 2s, so n becomes 9
• update result to 36 - 18 = 18

The next factor is 3.

• divide out all 3s, so n becomes 1
• update result to 18 - 6 = 12

Now n is fully factored, so phi(36) = 12.

That matches the count of numbers in the range 1 through 36 that are coprime with 36.

When you need totients for many numbers

If you need phi(n) for one number at a time, the factorization approach above is usually enough. If you need totients for every number up to a limit, a sieve-style algorithm is better.

1def phi_sieve(limit: int):
2    phi = list(range(limit + 1))
3
4    for i in range(2, limit + 1):
5        if phi[i] == i:
6            for j in range(i, limit + 1, i):
7                phi[j] -= phi[j] // i
8
9    return phi
10
11
12print(phi_sieve(10))

This uses the same prime-factor idea, but applies it to all multiples of each prime.

Why totient matters

Totient appears in:

• Euler’s theorem
• modular arithmetic
• RSA-style number theory discussions
• counting reduced fractions and coprime pairs

Even when the surrounding application is advanced, the core implementation is still about prime factors and repeated division.

Common Pitfalls

The biggest mistake is updating the result once for every repeated factor instead of once for each distinct prime factor. For example, 12 contains 2 twice, but the totient formula applies the factor 2 only once.

Another issue is forgetting the final if n > 1 step. That causes incorrect answers whenever the remaining unfactored part is a prime larger than the loop’s tested divisors.

Developers also sometimes compute totient by checking gcd(i, n) == 1 for every i. That is fine for demonstrations, but it is too slow compared with the factorization method for larger inputs.

Finally, remember that phi(1) is 1, which can surprise people who expect the count to start at zero.

Summary

• 'phi(n) counts integers from 1 to n that are coprime with n.'
• Efficient implementations use distinct prime factors, not repeated gcd checks.
• The core update is result -= result // p for each distinct prime factor p.
• A final leftover prime factor must still be applied after the main loop.
• Use a sieve approach when you need totients for many values, not just one.