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