Função totiente de Euler
Dado um número
n, a tarefa é calcular o resultado da função totiente de Euler.A função totiente de Euler calcula quantos números, entre 1 e
n, são coprimos de n. Em outras palavras, todos os números cujo máximo divisor comum com n seja igual a 1.
Entrada
A entrada contém um único inteiro
n (1 ≤ n ≤ ).Saída
O programa deve imprimir o resultado da função totiente de Euler para
n.Exemplos
Entrada | Saída |
20 | 8 |
9 | 6 |
Explicação
- 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