Bernhard
Registriertes Mitglied
Hallo zusammen,
ich beschäftige mich zur Zeit privat etwas mit der Programmierung des Siebes des Eratosthenes.
Allen Mathe- und Primzahl-Freunden wird das altbekannt sein, aber wer hat sich schon mal an die Programmierung desselben gewagt? Diejenigen, die das schon mal gemacht haben wissen, dass das recht schnell zu Speicherproblemen führen kann, wenn man damit auch Primzahlen mit mehr als zehn Stellen berechnen will.
Ein Blick auf den Pseudocode des WP-Artikels zeigt, dass auch dort von allen natürlichen Zahlen bis zum gewünschten Limit ausgegangen wird und das benötigt dann schnell auch sehr viel Speicher.
Meine Idee lautet nun, dass man die Startmenge an möglichen Zahlen vorab sinnvoll verkleinert. So kann man bei der Suche nach Primzahlen vorab trivialerweise alle geraden Zahlen streichen und reduziert damit die Größe des Siebes bereits um 50% !.
Das Sieb wird in diesem ersten Schritt also durch die Reihe
2 * n + 1
definiert, wobei n wieder in der Menge der natürlichen Zahlen größer oder gleich eins liegt.
Streicht man vorab die Vielfachen von 3, so erhält man nach relativ einfacher Rechnung die zwei Reihen:
6 * n + 1
6 * n + 5
wiederum mit n = 1, 2, 3, ...
streicht man weiter die Vielfachen von 5 erhält man die folgenden acht Reihen:
2*3*5 * n + 1
2*3*5 * n + 7
2*3*5 * n + 11
2*3*5 * n + 13
2*3*5 * n + 17
2*3*5 * n + 19
2*3*5 * n + 23
2*3*5 * n + 29
wiederum mit n = 1, 2, 3, ...
usw. und man erkennt dann auch, wie dieses Schema prinzipiell immer weiter fortgeführt werden kann. Man erhält auf diese Weise also immer bessere "übervollständige" Primzahlgeneratoren. Die D.h. die genannten Reihen produzieren immer alle Primzahlen, enthalten allerdings aber auch mehr oder weniger zusätzliche Zahlen, die nicht prim sind.
Über diese "Vorsiebung" kann man nun den benötigten Speicherplatz bei der Programmausführung für das vollständige Sieb stark reduzieren und ich würde nun gerne wissen, ob einer der Autoren oder Leser hier so etwas schon mal gemacht hat oder noch bessere Tricks zum Sieb des Eratosthenes kennt.
ich beschäftige mich zur Zeit privat etwas mit der Programmierung des Siebes des Eratosthenes.
Allen Mathe- und Primzahl-Freunden wird das altbekannt sein, aber wer hat sich schon mal an die Programmierung desselben gewagt? Diejenigen, die das schon mal gemacht haben wissen, dass das recht schnell zu Speicherproblemen führen kann, wenn man damit auch Primzahlen mit mehr als zehn Stellen berechnen will.
Ein Blick auf den Pseudocode des WP-Artikels zeigt, dass auch dort von allen natürlichen Zahlen bis zum gewünschten Limit ausgegangen wird und das benötigt dann schnell auch sehr viel Speicher.
Meine Idee lautet nun, dass man die Startmenge an möglichen Zahlen vorab sinnvoll verkleinert. So kann man bei der Suche nach Primzahlen vorab trivialerweise alle geraden Zahlen streichen und reduziert damit die Größe des Siebes bereits um 50% !.
Das Sieb wird in diesem ersten Schritt also durch die Reihe
2 * n + 1
definiert, wobei n wieder in der Menge der natürlichen Zahlen größer oder gleich eins liegt.
Streicht man vorab die Vielfachen von 3, so erhält man nach relativ einfacher Rechnung die zwei Reihen:
6 * n + 1
6 * n + 5
wiederum mit n = 1, 2, 3, ...
streicht man weiter die Vielfachen von 5 erhält man die folgenden acht Reihen:
2*3*5 * n + 1
2*3*5 * n + 7
2*3*5 * n + 11
2*3*5 * n + 13
2*3*5 * n + 17
2*3*5 * n + 19
2*3*5 * n + 23
2*3*5 * n + 29
wiederum mit n = 1, 2, 3, ...
usw. und man erkennt dann auch, wie dieses Schema prinzipiell immer weiter fortgeführt werden kann. Man erhält auf diese Weise also immer bessere "übervollständige" Primzahlgeneratoren. Die D.h. die genannten Reihen produzieren immer alle Primzahlen, enthalten allerdings aber auch mehr oder weniger zusätzliche Zahlen, die nicht prim sind.
Über diese "Vorsiebung" kann man nun den benötigten Speicherplatz bei der Programmausführung für das vollständige Sieb stark reduzieren und ich würde nun gerne wissen, ob einer der Autoren oder Leser hier so etwas schon mal gemacht hat oder noch bessere Tricks zum Sieb des Eratosthenes kennt.