Diskussion:Probedivision

In letzterem Fall benötigen die Primzahlen <1.872.851.947 nur ein Byte Speicherplatz.

Ist wohl ein Typo, ich weiss aber nicht, was der korrekte Speicherbedarf ist. --SirJective 15:54, 17. Dez 2003 (CET)

Nein, es ist wirklich nur ein Byte, also 8 Bit. Bis zu der gegebenen Zahl ist der Abstand zweier Primzahlen nie größer als 511, da man zusätzlich weiss, das Primzahlen ungerade sind, kann man die Hälfte des Abstandes speichern. Damit kommt man mit einem Byte aus. Vielleicht sollte man korrekter Schreiben: Ein Byte Speicherplatz pro Primzahl? Machts das klarer? --Berni 22:23, 17. Dez 2003 (CET)

Ich hab's jetzt mal etwas umformuliert. Ich glaube so wird es verständlicher, was gemeint ist.--Berni 22:47, 17. Dez 2003 (CET)

Ja, so wird's klar. (Diese Differenzmethode hab ich daheim auch schon angewandt, um eine Primzahl-Liste zu speichern.) --SirJective 20:28, 21. Dez 2003 (CET)

Irre Idee

Eine irre Idee: Fast 2 GB Daten erst zu berechnen und dann zu speichern (letzteres dauert wahrscheinlich viel länger), um weniger als einen Faktor 10 an Rechenoperationen zu sparen. Es ist ja ohnehin nur notwendig die 2 und die ungeraden Zahlen zu testen. Der Anteil der Primzahlen unter den Zahlen kleiner 10⁹ ist nach dem Primzahlsatz etwa 1/20 und 1/10, wenn man nur die ungeraden Zahlen betrachtet. In dem Artikel steht auch noch, wie ohne beträchtlichen Speicherbedarf noch etwa ein weiterer Faktor 2 gespart werden kann. Insgesamt benötigt ein PC selbst bei größeren Zahlen nur einige Sekunden bis Minuten für die Berechnung.

Deutlich schneller geht es, mit minimalem Speicherbedarf und der Pollard-Rho-Methode.

(nicht signierter Beitrag von Fsswsb (Diskussion | Beiträge) 23:41, 22. Apr 2006)

möglicher Fehler

Die verbleibende Zahl ist dann eine Primzahl und der letzte Faktor von $n$, da sie zum einen durch keine der Zahlen kleiner ${\sqrt {n}}$ teilbar ist und zum anderen das Produkt zweier Zahlen größer ${\sqrt {n}}$ auch größer als $n$ selbst ist. 

Aus dem Text der Probedivisionsseite. So formuliert ergiebt sich eine Irreführung. Reduziert man das auf eine Formel so ist $n$ größer als $n$ selbst und das ergiebt für mich keinen Sinn. (nicht signierter Beitrag von 79.243.33.63 (Diskussion) 12:32, 18. Nov. 2012 (CET))

Implementierungsdetails

Dieser Teil hier scheint mir fragwürdig: "Anstatt zu überprüfen, ob p größer als die Wurzel aus n ist, testet man ob p² größer als n ist, da dies schneller geht."

sqrt(n) kann man einmal ausrechnen und dann muss man nur noch vergleichen, p^2 erfordert eine Multiplikation für jede einzelne Zahl entlang des Weges. --134.130.4.241 16:10, 21. Mär. 2015 (CET)