Funzione totiente di Eulero
Dato un numero
n, devi calcolare il valore della funzione totiente di Eulero.La funzione totiente di Eulero conta quanti interi da 1 a
n sono coprimi con n. In altre parole, conta tutti i numeri il cui massimo comune divisore con n è pari a 1.
Ingresso
L’ingresso contiene un singolo intero
n (1 ≤ n ≤ ).Uscita
Il programma deve stampare il risultato della funzione totiente di Eulero per
n.Esempi
Input | Output |
20 | 8 |
9 | 6 |
Spiegazione
- 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