Euler's Totient Function
Factor an integer and apply the multiplicative product formula to count smaller coprime values.
Core idea
Factor n into distinct primes. For each prime p, remove the one-in-p fraction of candidates divisible by p, producing the product n times one minus one over p.
Read the visualization
Candidate integers are crossed out when a discovered prime factor divides them. The product column updates once per distinct factor, not once per exponent.
1
2
3
4
5
6
7
8
9
10
11
12
Begin with all candidates below n and the product result equal to n.
Complexity and tradeoffs
Time: O(sqrt n) trial division. Space: O(1). Each distinct prime factor p multiplies the running result by (1 - 1/p).
Invariant: After processing a set of prime factors, the surviving candidates are divisible by none of those factors.
Where it fits
Euler's phi function controls multiplicative groups modulo n, Euler's theorem, modular inverses, RSA reasoning, and reduced-fraction counts.