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