PreviousNext
Coding/Arrays and strings

Euler totient

Write codeMedium25 min

Your task

Compute Euler's totient phi(n): the count of integers in [1, n] that are coprime to n. For example phi(9) = 6 (1,2,4,5,7,8). Constraints: 1 <= n <= 1e12, with phi(1) = 1 by convention. Use the product formula over distinct prime factors; do not loop over all integers up to n.

Examples

euler_totient(n: int) -> int
Example 1
Inputeuler_totient(9)
Output6