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