Ich versuche einen effizienten Weg zu finden, Eulers Totient-Funktion zu berechnen.
Was ist falsch an diesem Code? Es scheint nicht zu funktionieren.
%Vor%Hier ist ein viel schnellerer, funktionierender Weg, basierend auf dieser Beschreibung auf Wikipedia:
Wenn also n eine positive ganze Zahl ist, dann ist φ (n) die Zahl der ganzen Zahlen k im Bereich 1 ≤ k ≤ n, für die gcd (n, k) = 1 gilt.
Ich sage nicht, dass dies der schnellste oder sauberste ist, aber es funktioniert.
%Vor%Sie haben drei verschiedene Probleme ...
y muss gleich n als Anfangswert sein, nicht 1
n % i == 0 is True tut nicht, was du denkst, weil Python die Vergleiche verkettet hat! Auch wenn n % i gleich 0 ist dann 0 == 0 ist True ABER 0 is True ist False ! Verwende parens oder entferne einfach den Vergleich mit True , da das sowieso nicht nötig ist. Behebung dieser Probleme,
%Vor%Es sieht so aus, als ob Sie Eulers Produktformel verwenden möchten, aber Sie berechnen nicht die Anzahl der Primzahlen, die a teilen. Sie berechnen die Anzahl der Elemente, die relativ zu a prim sind.
Da 1 und i beide Ganzzahlen sind, gilt dies auch für die Division. In diesem Fall erhalten Sie immer 0.
In Bezug auf die Effizienz habe ich nicht bemerkt, dass jemand erwähnt, dass gcd (k, n) = gcd (n-k, n). Durch die Verwendung dieser Tatsache kann etwa die Hälfte der Arbeit eingespart werden, die für die Methoden zur Verwendung des gcd erforderlich ist. Starten Sie einfach die Zählung mit 2 (weil 1 / n und (n-1) / k immer irreduzibel ist) und addieren Sie jedes Mal, wenn das gcd eins ist, 2.
Eigentlich, um phi zu berechnen (irgendeine Zahl sagen n)
Wir verwenden die Formel
wo p die Primfaktoren von n sind.
Sie haben also wenige Fehler in Ihrem Code:
1. y sollte gleich n sein
2. Für 1/i tatsächlich 1 und i sind beide Ganzzahlen, also wird ihre Auswertung auch eine ganze Zahl sein, daher wird es zu falschen Ergebnissen führen.
Hier ist der Code mit den erforderlichen Korrekturen.
%Vor%Tags und Links python
