Problem
Die Eulersche Phi-Funktion φ(n) zählt die ganzen Zahlen k mit 1 ≤ k ≤ n und ggT(k, n) = 1. Zum Beispiel ist φ(9) = 6, denn 1, 2, 4, 5, 7 und 8 haben mit 9 keinen gemeinsamen Teiler.
Implementiere eulers_totient(n).
Jedes k einzeln zu prüfen ist für n bis 10^12 zu langsam. Verwende stattdessen die Produktformel: φ(n) = n × (1 − 1/p) für jede verschiedene Primzahl p, die n teilt. Rechnest du das ganzzahlig als n / p × (p − 1), vermeidest du Brüche.
Eingabe
n: Eine positive ganze Zahl.
Ausgabe
Gib φ(n) zurück. Nach der Definition gilt φ(1) = 1.
Einschränkungen
1 ≤ n ≤ 10^12
Beispiele
Eingabe:
n = 36
Erwartete Ausgabe:
expected = 12
Eingabe:
long long n = 36;
Erwartete Ausgabe:
long long expected = 12;
Eingabe:
long n = 36;
Erwartete Ausgabe:
long expected = 12;
Erläuterung
36 = 2² × 3², also ist φ(36) = 36 × (1 − 1/2) × (1 − 1/3) = 36 × 1/2 × 2/3 = 12.
Eingabe:
n = 13
Erwartete Ausgabe:
expected = 12
Eingabe:
long long n = 13;
Erwartete Ausgabe:
long long expected = 12;
Eingabe:
long n = 13;
Erwartete Ausgabe:
long expected = 12;
Erläuterung
13 ist prim, also ist jedes k von 1 bis 12 teilerfremd zu 13, und φ(13) = 12.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Zerlege n per Probedivision bis √n in Primfaktoren.
Hinweis 2
Ersetze das Ergebnis für jede verschiedene Primzahl p durch Ergebnis / p × (p − 1); teile zuerst, damit der Wert klein bleibt.
Hinweis 3
Ein Restfaktor größer als 1 nach der Schleife ist ebenfalls eine Primzahl.
Erwartete Komplexität
Zeit O(√n), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.