Euler's totient sieve

O(n log log n)

Euler's totient φ(n) is the count of integers in 1..n that are coprime to n — the building block of modular arithmetic and RSA. Instead of testing each number, a sieve computes all of them together. Start with φ[i] = i. Sweep i upward; the first time you meet an i still equal to its start value it must be prime, so apply φ ← φ·(1 − 1/i) to every multiple of i. After all primes ≤ n are handled, each φ[m] is the product over its prime factors p of (1 − 1/p), exactly the totient. It runs in O(n log log n), like the prime sieve it mirrors. Primes light up green (φ(p) = p − 1) and the small number in each cell is its current φ.

Numbers
Edit the input and press Play

How it works

  1. Set φ[i] = i for every i.
  2. Sweep up; an i untouched so far is prime.
  3. For each multiple m of that prime, scale φ[m] by (1 − 1/p).
  4. When the sweep ends, every φ is final.

Pseudocode

1totientSieve(n):                    # O(n log log n)2  phi[i] ← i  for all i3  for i from 2 to n:4    if phi[i] = i:                   # i is prime5      for m from i to n step i:6        phi[m] ← phi[m] − phi[m]/i   # apply (1 − 1/i)7  return phi