Euler's totient function
For a given number
n, you are asked to calculate the result of Euler’s totient function.Euler’s totient function calculates the number of integers from 1 to
n that are relatively prime to n. Meaning all the numbers with the greatest common divisor with n equal to 1.
Input
The input contains a single integer
n (1 ≤ n ≤ ).Output
The program should print the result of Euler's totient function for
n.Examples
Input | Output |
20 | 8 |
9 | 6 |
Explanation
- 20 → 1, 3, 7, 9, 11, 13, 17, 19
- 9 → 1, 2, 4, 5, 7
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB