Euler Totient Function

Compute φ(n) for positive integers using an efficient algorithm.

math number-theory totient

Euler's totient function φ(n) counts the number of positive integers from 1 to n that are coprime with n (i.e., have gcd(k, n) = 1). Write a function `totient(n)` that returns φ(n) for a positive integer n. The solution must handle n up to 10^6 efficiently (Hint: factorize n or use a sieve-like method).

Constraints

1 ≤ n ≤ 10^6. Time limit: O(sqrt(n)) per call is acceptable for a single call, but O(n log log n) precomputation is fine if you plan multiple calls (not required). Your function should be deterministic and return an integer.

Example

>>> totient(1)
1
>>> totient(2)
1
>>> totient(10)
4
>>> totient(9973)
9972

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Recall that if n = p1^a1 * p2^a2 * ... * pk^ak, then φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk).

You can compute the prime factors by trial division up to sqrt(n).

Use integer arithmetic to avoid floating point errors: multiply by (p-1) and divide by p.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.