Diskussion:Algorithmensammlung: Zahlentheorie: Primfaktorisierung

Andere Verfahren

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

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)

Abbruchbedingung

Die Schleife zum Testen der Teilbarkeit muss nicht bis ${\frac {n}{2}}$ durchlaufen werden, sondern nur bis ${\sqrt {n}}$ (einschließlich). Zerlegt man eine beliebige natürliche Zahl $n$ (zum Beispiel 14, siehe oben!) in zwei Faktoren, so ist ein Faktor (hier 2) kleiner oder gleich ${\sqrt {n}}$, der andere (hier 7) größer oder gleich ${\sqrt {n}}$. Natürlich darf man diesen zweiten Faktor in der Liste nicht vergessen.

Irritierend finde ich auch, wenn die Python-Version bei einer Primzahl eine leere Liste ausgibt. --188.98.222.209 18:11, 17. Okt. 2020 (CEST)