Diskussion:Algorithmensammlung: Zahlentheorie: Primfaktorisierung

Aus Wikibooks
Zur Navigation springen Zur Suche springen

Andere Verfahren[Bearbeiten]

Meine Güte, auf die Idee mit itertools wär' ich nie gekommen. Und ich dachte, ich beherrsche Python schon ganz ordentlich... Was hältst Du von dieser Funktion hier (Abschnitt "Implementierung des Verfahrens)? Warum genau lässt Du range() bis (n+1)//2+1 laufen? Was hältst Du vom Erzeugen aller Primzahlen bis n mit dem Sieb des Erastothenes und anschließendem Testen? Ich versuch' mich auch noch mal irgendwann an einer Implementierung der Primzahlzerlegung nach Fermat. Tut mir leid, dass ich so viel Scherereien bereite, aber ich bin noch recht unerfahren in der Hohen Schule der Mathematik und Programmierung. MfG 84.159.208.151 15:01, 7. Mär. 2015 (CET)

(n+1) // 2 = ceil(n/2), und das ist der größte Faktor (neben n selbst), den es geben kann: Jede Zahl, die echt zwischen n/2 und n liegt, muss man mit einer Zahl kleiner als 2 multiplizieren, um bei n anzukommen. Das Sieb des Erastothenes explizit zu erzeugen bringt vermutlich nur einen Geschwindigkeitsvorteil, wenn man viele Zahlen faktorisieren muss. Ein Beispiel, warum man n/2 statt der Wurzel braucht, ist n=14. Die Wurzel ist 3.74, die korrekte Faktorisierung ist aber 14=2·7. -- Pberndt 17:32, 7. Mär. 2015 (CET)
Danke.2003:84:AE04:4412:5075:E3C3:ACBF:CD8E 18:49, 7. Mär. 2015 (CET)

Implementierung weicht von Spezifikation ab[Bearbeiten]

Die vorliegende Python Implementierung (Version 19:49, 7. Mär. 2015‎) macht nicht genau das, was beschrieben ist ("Die Funktion bekommt eine natürliche Zahl n größer als 0 übergeben und liefert eine Liste sämtlicher Primfaktoren von n, von 1 und n selbst abgesehen, zurück. Wenn n eine Primzahl ist, wird eine leere Liste zurückgegeben."):

Für n=2 wird [2] als Ergebnis geliefert, also nicht eine leere Liste wie spezifiziert. Nach meinem Verständnis von Primfaktorenzerlegung wäre [2] auch das richtige Ergebnis, jedoch wird für alle anderen Primzahlen eine leere Liste zurückgeliefert, was ich zumindest für inkonsistent halte. -- Yaccob 15:46, 05. Sep. 2016 (Signatur nachgetragen von: Pberndt 15:53, 5. Sep. 2016 (CEST)-- bitte signiere deine künftigen Beiträge selbst mit 4 Tilden ~~~~)

Stimmt, das sollte geändert werden — nur zu! -- Pberndt 15:55, 5. Sep. 2016 (CEST)