Función totiente de Euler
Para un número dado n, se solicita calcular el resultado de la función totiente de Euler.
La función totiente de Euler calcula cuántos enteros del 1 al n son coprimos con n. Es decir, todos aquellos números que tienen un máximo común divisor con n igual a 1.
Entrada
La entrada contiene un solo entero n (1 ≤ n ≤ ).
Salida
El programa debe imprimir el resultado de la función totiente de Euler para n.
Ejemplos
Input | Output |
|---|---|
20 | 8 |
9 | 6 |
Explicación
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