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.
1function phi(n: number): number {
2 let res = n; // from n init
3 for (let p = 2; p * p <= n; p++) {
4 if (n % p !== 0) continue; // trial division: find prime factor
5 res -= res / p; // multiply (1 − 1/p): cross
6 while (n % p === 0) n /= p; // cross count prime factor
7 }
8 if (n > 1) res -= res / n; // survive one survive prime factor
9 return res; // survive count = φ(n)
10}
n12 = 2²·3
targetφ(12) = and 12 coprime count
res12
1 / 7
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.