Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
φ(n) counts the integers in [1, n] that are coprime to n. For a single n, factorise it and apply the product formula φ(n) = n · ∏(1 − 1/p) over its distinct prime factors p — computed overflow-safely as φ = φ / p * (p − 1). That's O(√n) per value. To get φ for every value up to n at once, run a sieve that seeds φ[i] = i and, for each prime p, multiplies the (1 − 1/p) factor into every multiple of p — O(n log log n) total.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you know the product formula φ(n) = n·∏(1 − 1/p), can apply it once per distinct prime overflow-safely, and can adapt the sieve to compute φ for an entire range.
Where candidates slip
Applying the (1 − 1/p) factor once per prime *occurrence* instead of per distinct prime, or computing n*(p−1)/p in an order that overflows or loses integrality.
How to stand out
Justify the formula from inclusion–exclusion (subtract multiples of each prime, add back overlaps) or from multiplicativity, and note the sieve variant reuses the Eratosthenes skeleton to get all φ values in O(n log log n).
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewresult = n, temp = np*p <= temp ?NoYesExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 3
Count Coprimes by GCD (Baseline)
1Hint 1Explore hintHide hint
The definition is literal: φ(n) is how many k in [1, n] have gcd(k, n) = 1. What's the most direct way to compute that?
2Hint 2Explore hintHide hint
Loop k from 1 to n, compute gcd(k, n), and count the ones equal to 1.
3Hint 3Explore hintHide hint
Each gcd is O(log n) and you do n of them → O(n log n). Fine for small n, but can you avoid touching every k?
A · Core idea
The definition says φ(n) = |{k ∈ [1, n] : gcd(k, n) = 1}|. So loop k from 1 to n, run the Euclidean gcd against n, and tally the coprimes.
Why this is unambiguously correct. It computes exactly what the definition states — no number theory required beyond gcd. It's the reference implementation you'd use to verify the faster formula on small inputs.
Why it doesn't scale. It visits every integer up to n. For n = 10⁹ that's a billion gcd calls — far too slow. The product formula gets the same answer in O(√n) by reasoning about n's prime factors instead of scanning all of [1, n].
Why the formula can replace it. Coprimality to n depends only on n's prime factors: k is coprime to n exactly when k shares none of n's primes. So instead of testing each k, we discount the fraction of numbers killed by each prime — that's the (1 − 1/p) factor — and never enumerate at all.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 10k=1
gcd(1,10)=1
count=14C · Code with teaching comments
Reference implementation previewpublic long phiByCount(long n) { long count = 0; for (long k = 1; k <= n; k++) { if (gcd(k, n) == 1) count++; }Explore the full codeHide the full code
D · Why it works and complexityO(n log n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The gcd-count baseline is the ground truth: it computes the definition directly and is perfect for validating the formula on small n. Its weakness is purely that it enumerates all of [1, n] rather than exploiting that coprimality is decided entirely by n's prime factors.
ComplexityO(n log n) time, O(1) space — n iterations, each computing a gcd in O(log n), gives O(n log n). Only a counter is stored, so O(1) extra space.
E · Edge cases and pitfalls3Running this for n up to 10⁹ — a billion gcd calls is far too slow.Explore edge casesHide edge cases
Pitfalls
- Running this for n up to 10⁹ — a billion gcd calls is far too slow.
- Starting k at 0 — gcd(0, n) = n ≠ 1, harmless to the count but conceptually wrong; the range is [1, n].
- Re-implementing gcd incorrectly (wrong stop condition) so the count is off.
Approach 2 of 3 · Optimal
Product Formula via Factorisation (Optimal, single n)
1Hint 1Explore hintHide hint
Coprimality to n only depends on which of n's prime factors a number avoids. For a single prime p dividing n, what fraction of [1, n] is NOT a multiple of p?
2Hint 2Explore hintHide hint
Exactly (1 − 1/p) of them avoid p. Because distinct primes are independent, multiply these fractions: φ(n) = n · ∏(1 − 1/p) over distinct primes p | n.
3Hint 3Explore hintHide hint
Factorise n by trial division up to √n. For each distinct prime found, do φ = φ / p * (p − 1), and strip all copies of p before moving on.
A · Core idea
Use φ(n) = n · ∏_{p | n} (1 − 1/p), the product over n's distinct prime divisors. Factorise n by trial division to √n; for each distinct prime p, apply the factor; if a prime > √n remains at the end, apply its factor too.
Why each prime contributes (1 − 1/p) — inclusion–exclusion. Among 1..n, exactly n/p are multiples of p (hence not coprime to n through p). Removing them leaves n(1 − 1/p). For a second prime q, a q-fraction of those must also go, leaving n(1 − 1/p)(1 − 1/q). The cross-term (multiples of both p and q) is corrected automatically because (1 − 1/p)(1 − 1/q) expands to 1 − 1/p − 1/q + 1/(pq) — the +1/(pq) is exactly the inclusion–exclusion add-back for numbers divisible by both. So multiplying the per-prime factors is inclusion–exclusion over the prime divisors. Equivalently, φ is multiplicative: φ(ab) = φ(a)φ(b) for coprime a, b, and φ(p^k) = p^k − p^(k−1) = p^k(1 − 1/p), which the product reproduces.
Why only DISTINCT primes. The factor (1 − 1/p) accounts for all multiples of p in one shot, regardless of how many times p divides n. For n = 12 = 2²·3, the prime 2 still removes exactly the even numbers once — applying (1 − 1/2) twice would wrongly discount them again. The exponent of p affects the leading n, not the number of factors.
Why φ = φ / p * (p − 1) is overflow-safe and exact. At the moment we process prime p, the running value is still divisible by p (we haven't removed p's contribution yet), so φ / p is an exact integer — no rounding. Dividing before multiplying by (p − 1) keeps the intermediate ≤ the current φ, avoiding the overflow that n * (p − 1) / p would risk. Writing it as n * (1 − 1/p) in floating point would introduce rounding error; integer order is both exact and safe.
Why the leftover handles the large prime. After dividing out every prime ≤ √n, any value still greater than 1 must be a single prime larger than √n (a number ≤ n can have at most one prime factor exceeding √n). Apply its (1 − 1/p) factor as the final step.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 12Array state
init
result = 12, temp = 12
4 (coprime to 12: 1, 5, 7, 11)C · Code with teaching comments
D · Why it works and complexityO(√n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The formula turns a counting problem into a factorisation problem: coprimality is decided entirely by n's distinct primes, so you discount each prime's fraction once and stop. The integer order φ/p*(p−1) is the crux — it's exact because φ is still divisible by p at that point, and overflow-safe because you shrink before you grow.
ComplexityO(√n) time, O(1) space — Trial division tests divisors up to √n, so O(√n). Each distinct prime triggers one O(1) update. The final leftover prime (if any) is one more O(1) step. O(1) extra space.
E · Edge cases and pitfalls7n = 1 — Loop doesn't run (p*p > 1), temp stays 1, no leftover → result = 1 = φ(1).Explore edge casesHide edge cases
Edge cases handled
n = 1Loop doesn't run (p*p > 1), temp stays 1, no leftover → result = 1 = φ(1).n = prime (e.g. 7)No p ≤ √7 divides 7; leftover temp = 7 > 1 → 7/7*6 = 6 = φ(7).n = p^k (e.g. 8)p=2 strips to temp 1; result = 8/2*1 = 4 = φ(8) = 8 − 4.
Pitfalls
- Applying (1 − 1/p) once per occurrence of p instead of once per distinct prime.
- Writing result = result * (p − 1) / p — the multiply can overflow before the divide; divide first.
- Forgetting the leftover temp > 1 check — drops the single large prime factor.
- Using floating point n * (1 − 1.0/p) — rounding errors corrupt the integer result.
Approach 3 of 3
Totient Sieve for All Values up to N
1Hint 1Explore hintHide hint
Seed phi[i] = i for all i. If you process primes in increasing order, how can each prime p update φ for all its multiples at once?
2Hint 2Explore hintHide hint
When p is prime (detected because phi[p] is still p), walk every multiple m of p and apply the (1 − 1/p) factor: phi[m] -= phi[m] / p.
3Hint 3Explore hintHide hint
Because primes are processed in order and each multiple gets each of its prime factors applied exactly once, phi[m] ends as the correct totient. This is the sieve skeleton with a multiplicative update.
A · Core idea
Initialise phi[i] = i for every i in [0, N]. Sweep i from 2 to N. When phi[i] still equals i, i is prime — so for every multiple m of i, apply i's factor with phi[m] -= phi[m] / i (which multiplies phi[m] by (1 − 1/i)).
Why phi[i] == i detects a prime. We only ever reduce phi[m] when we process a prime factor of m. If i had any prime factor smaller than itself, that smaller prime would already have reduced phi[i] below i. So phi[i] still equal to i means no smaller prime divides i — i is prime. This is the same 'untouched survivor is prime' logic as Eratosthenes.
Why the update is correct. phi[m] -= phi[m] / i is exactly phi[m] · (1 − 1/i): at the moment prime i is applied to m, phi[m] is still a multiple of i (no earlier step removed i's contribution), so phi[m]/i is exact. Each multiple m receives the factor for each of its distinct primes exactly once, in increasing prime order, so by the time we've processed every prime ≤ N, phi[m] equals m · ∏(1 − 1/p) over m's primes — the totient. The product formula and the sieve compute the same thing; the sieve just amortises the work across the whole range.
Why it's near-linear. Identical accounting to Eratosthenes: prime i edits N/i entries, and Σ N/i over primes is O(N log log N). One pass builds φ for all values, which beats running the O(√n) single-value routine N times (≈ O(N√N)).
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
N = 6Array state
seed
phi[i] = i
phi[1..6] = [1, 1, 2, 2, 4, 2]C · Code with teaching comments
Reference implementation previewpublic int[] totientSieve(int n) { int[] phi = new int[n + 1]; for (int i = 0; i <= n; i++) phi[i] = i; for (int i = 2; i <= n; i++) { if (phi[i] == i) { // i is primeExplore the full codeHide the full code
D · Why it works and complexityO(N log log N) timeO(N) spaceOpen the invariant and proofExplore the proofHide the proof
The totient sieve is the Eratosthenes skeleton with one change: instead of marking a multiple as composite, you fold the prime's (1 − 1/p) factor into it. The same 'untouched means prime' detection and the same N·Σ(1/p) cost analysis carry over verbatim — a clean example of reusing a known skeleton to compute a multiplicative function over a range.
ComplexityO(N log log N) time, O(N) space — Like the Sieve of Eratosthenes, each prime p touches N/p multiples; summing N/p over primes ≤ N gives N·Σ(1/p) = O(N log log N). The array is O(N) space.
E · Edge cases and pitfalls7N = 1 — Loop from 2 doesn't run; phi = [0, 1], so φ(1) = 1.Explore edge casesHide edge cases
Edge cases handled
N = 1Loop from 2 doesn't run; phi = [0, 1], so φ(1) = 1.phi[0]Stays 0 (undefined totient); ignore index 0 in any downstream use.prime p ≤ Nphi[p] == p triggers the update phi[p] -= 1 → p − 1 = φ(p).
Pitfalls
- Reordering the update so phi[m] is no longer divisible by i — breaks the exact integer division.
- Detecting primes with a separate sieve instead of the phi[m] == m trick — works but redundant.
- Starting the inner loop at i*i (as in Eratosthenes) — here you must start at i, because i itself and every multiple needs the factor.
- Using O(N√N) by calling the single-value φ N times instead of one sieve pass.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic long phi(long n) { long result = n; long temp = n; for (long p = 2; p * p <= temp; p++) { if (temp % p == 0) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Factor applied per occurrence, not per distinct prime
For n = 12 = 2²·3, the prime 2 disqualifies the even numbers exactly once. Applying (1 − 1/2) for each of the two 2s double-counts and gives the wrong totient.
Explore the code comparisonHide the code comparison
Factor applied per occurrence, not per distinct prime
For n = 12 = 2²·3, the prime 2 disqualifies the even numbers exactly once. Applying (1 − 1/2) for each of the two 2s double-counts and gives the wrong totient.
Don't write this
while (temp % p == 0) {
result = result / p * (p - 1); // applied per occurrence — WRONG
temp /= p;
}Write this instead
if (temp % p == 0) {
while (temp % p == 0) temp /= p; // strip all copies first
result = result / p * (p - 1); // apply once per distinct prime
}2Multiply-before-divide overflow
result * (p − 1) can overflow before the division, and floating n*(1−1.0/p) introduces rounding. result / p is exact here because result is still divisible by p, so divide first.
Explore the code comparisonHide the code comparison
Multiply-before-divide overflow
result * (p − 1) can overflow before the division, and floating n*(1−1.0/p) introduces rounding. result / p is exact here because result is still divisible by p, so divide first.
Don't write this
result = result * (p - 1) / p; // overflow risk / order mattersWrite this instead
result = result / p * (p - 1); // exact and overflow-safe3Dropping the large leftover prime
After trial division to √n, a value > 1 may remain — a prime factor bigger than √n. Skipping it omits one factor and overstates φ.
Explore the code comparisonHide the code comparison
Dropping the large leftover prime
After trial division to √n, a value > 1 may remain — a prime factor bigger than √n. Skipping it omits one factor and overstates φ.
Don't write this
while p * p <= temp:
...
return result # forgets temp > 1 caseWrite this instead
while p * p <= temp:
...
if temp > 1:
result = result // temp * (temp - 1)
return resultRevise
Carry the pattern into the interview
Pattern to remember
Prime-factorisation product formula; sieve for all values
Code pattern to memorize
single n: φ = n
for each prime p | n: φ = φ / p * (p - 1)
(one factor per DISTINCT prime)
sieve up to N: phi[i] = i
for p in 2..N if phi[p]==p (p is prime):
for m in p, 2p, ..: phi[m] -= phi[m] / pRules to remember
- 1Apply the (p − 1)/p factor once per distinct prime, not once per occurrence — strip out all copies of p after the first.
- 2Compute the factor as
φ / p * (p − 1), dividing first: φ is always divisible by p at that point, and this avoids overflow. - 3In the sieve,
phi[p] == pstill holds exactly when p is prime (nothing smaller touched it) — that's the primality test for free. - 4φ(1) = 1 (the empty product / by convention), and φ(p) = p − 1 for any prime p.
- 5After dividing n by all factors, if a leftover > 1 remains it's a prime factor too (the single large prime) — apply its factor.
Use this pattern when
- Count integers in [1, n] coprime to n (gcd = 1)
- Euler's theorem: reduce huge exponents mod n via a^φ(n) ≡ 1 (mod n) for gcd(a,n)=1
- Sum or count over residues / primitive roots / fraction reduction problems
- You need φ for a whole range → totient sieve in near-linear time
Choose another pattern when
- You only need gcd of two numbers → Euclid, not totient
- n is a giant semiprime you can't factor → totient is as hard as factoring (this underpins RSA)
- You need the actual coprime numbers, not the count → enumerate with gcd checks
- Modulus isn't fixed / structure differs → reconsider the tool
Interview takeaway
Euler's totient is multiplicativity in action: φ(n) factors through the primes of n via ∏(1 − 1/p). For one number, factorise and multiply the factors; for a whole range, push each prime's factor through its multiples with a sieve. The same 'cross out / fold in per prime' skeleton as the Sieve of Eratosthenes, repurposed to compute a multiplicative function.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical multiplicative-function-over-primes. φ(n) = n·∏(1 − 1/p) is the template: decompose by distinct primes for one value, or push each prime's factor through its multiples with a sieve for a whole range. The same shape computes the number/sum of divisors and the Möbius function.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Sieve of EratosthenesThe totient sieve is the same skeleton; learn the cross-out version first.
- Sum of Totients (Totient Summatory)Coming soonΣφ(i) for i ≤ n; build on the totient sieve, or use a divisor/Mobius trick for huge n.
- Modular Inverse via EulerComing soonFor gcd(a,n)=1, a⁻¹ ≡ a^(φ(n)−1) mod n — combine totient with modular exponentiation.
- Modular ExponentiationEuler's theorem reduces huge exponents mod n using φ(n); fast power finishes the job.