Next, Rafid needs Euler's totient function — counting integers up to N that share no common factor with N. Read N. Print φ(N), the count of integers in [1,N] coprime with N, computed via prime factorization in O(sqrt(N)).
Input
One integer N.
Output
φ(N).
Constraints
1 ≤ N ≤ 10^12
Sample Input
9
Sample Output
6
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.