Fonction indicatrice d’Euler
Pour un nombre
n donné, vous devez calculer la valeur de la fonction indicatrice d’Euler.La fonction indicatrice d’Euler calcule le nombre d’entiers entre 1 et
n qui sont premiers avec n. Autrement dit, tous ceux dont le plus grand diviseur commun avec n est égal à 1.
Données d’entrée
Les données d’entrée contiennent un seul entier
n (1 ≤ n ≤ ).Sortie
Le programme doit afficher le résultat de la fonction indicatrice d’Euler pour
n.Exemples
Input | Output |
20 | 8 |
9 | 6 |
Explications
- 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