Eulers Totientfunktion
Für eine gegebene Zahl n sollen Sie den Wert von Eulers Totientfunktion berechnen.
Eulers Totientfunktion ermittelt die Anzahl aller ganzen Zahlen von 1 bis n, die zu n teilerfremd sind. Das bedeutet, es werden alle Zahlen gezählt, deren größter gemeinsamer Teiler mit n gleich 1 ist.
Eingabe
Die Eingabe besteht aus einer einzelnen ganzen Zahl n (1 ≤ n ≤ ).
Ausgabe
Das Programm soll das Ergebnis von Eulers Totientfunktion für n ausgeben.
Beispiele
Input | Output |
|---|---|
20 | 8 |
9 | 6 |
Erklärung
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