Euler Totient of n
HardMathNumber Theory
Description
Given a positive integer n, return Euler's totient phi(n): the number of integers in [1, n] coprime to n.
Examples
Input:
n = 1Output:
1Explanation:
For n = 1 the only integer in [1,1] is 1, which is coprime to 1, so phi(1) = 1.
Input:
n = 9Output:
6Explanation:
Integers in [1,9] coprime to 9 are 1, 2, 4, 5, 7, 8 — six in total, so phi(9) = 6.
Input:
n = 36Output:
12Explanation:
Using the factorization 36 = 2^2 * 3^2, phi(36) = 36 * (1-1/2) * (1-1/3) = 12.
Constraints
- •
1 ≤ n ≤ 10¹²