Sieb des Eratosthenes

**Bernhard** · 06.01.2022, 22:42

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.

**Bernhard** · 09.01.2022, 01:59

Beschränkt man sich nur auf ungerade Zahlen kann man den Speicherbedarf eines Programmes bereits deutlich reduzieren (< 500 MB anstelle < 1GB) und kann innerhalb des Wertebereiches des Datentyps long (32 Bit) ohne nennenswerte Rechenzeit (< 1 Minute) immerhin alle Primzahlen < x = 1e9 berechnen.

Die komplizierteren Formeln bringen mMn keine nennenswerten Vorteile, weil das Programm dadurch deutlich unübersichtlicher wird und die Reduzierung von Speicherbedarf und Rechenzeit vergleichsweise gering bleiben.

Interessant erscheint mir dagegen die Berechnung der Primzahlfunktion für die Werte x >= 1e10. Dazu gibt es dann auch weiterführende Literatur, wie zB: https://primes.utm.edu/howmany.html

**ralfkannenberg** · 09.01.2022, 11:28

Zitat von Bernhard

Interessant erscheint mir dagegen die Berechnung der Primzahlfunktion für die Werte x >= 1e10.

Halo Bernhard,

was Du hier machen kannst ist Zahlen mit Hilfe zweier Varialen zusammenzusetzen, d.h. die ersten 10 Stellen eines Primzahlkandidaten in einer Variablen und die anderen 10 Stellen in der anderen Variablen.

Dann musst Du zwar die vier Grundrechenarten selber programmieren, aber im Falle der Addition und Subtraktion ist das sehr einfach und bei der Division machst Du das eben so wie man von Hand dividiert, d.h. die nächste noch nicht berücksichtigte Stelle "hinunterziehen" und dann die "Zwischensumme" dividieren.

Ausserdem kann man, falls man aus irgendeinem Grunde gewisse Primzahlen immer wieder neu ermitteln muss, diese in einer Tabelle zwischenspeichern und dann nur die Tabelle durchgehen, das hat damals meine Berechnung wesentlich beschleunigt. Damals ging es mir um die Fragestellung, wie viele Primzahlen ich von einer geraden natürlichen Zahl abziehen kann und das Ergebnis ist jedesmal eine Nicht-Primzahl. Also konkret um die Funktion g(n) = kleinste gerade natürliche Zahl, von der man die ersten n Primzahlen subtrahieren kann und das Ergebnis ist eine Nicht-Primzahl.

Praktisch war auch, dass - da ich ja die kleinste von denen gesucht habe - ich an der Uni alle verfügbaren Rechner über das Wochenende in benachbarten Zahlenintervallen laufen lassen konnte, das ganze so abgeschätzt, dass meine Berechnungen am Montag früh um 6 Uhr abgeschlossen waren, damit dann die ersten Studenten nicht blockiert waren. Die Ergebnisse habe ich in einer Datei verspeichert und diese dann am Montag in der Mittagspause ausgedruckt. Somit ergaben sich verschiedene Kandidaten für g(n) und der absolut-kleinste war dann die gesuchte Zahl. Hierbei ist noch anzumerken, dass bei grösseren Zahlen pro Zehnerpotenz vielleicht 3 Hits zu erwarten sind, d.h. mit einer Ausnahme war jedesmal die gefundene Zahl schon das gesuchte Minimum, und in den allermeisten Fällen gab es keine Hits.

Freundliche Grüsse, Ralf

**Bernhard** · 09.01.2022, 20:34

Hallo Ralf,

Zitat von ralfkannenberg

was Du hier machen kannst ist Zahlen mit Hilfe zweier Varialen zusammenzusetzen, d.h. die ersten 10 Stellen eines Primzahlkandidaten in einer Variablen und die anderen 10 Stellen in der anderen Variablen.

Dann musst Du zwar die vier Grundrechenarten selber programmieren, aber im Falle der Addition und Subtraktion ist das sehr einfach und bei der Division machst Du das eben so wie man von Hand dividiert, d.h. die nächste noch nicht berücksichtigte Stelle "hinunterziehen" und dann die "Zwischensumme" dividieren.

interessant, aber mittlerweile geht das mMn einfacher, wenn man gleich in Python programmiert. Dort kann man direkt mit beliebig großen ganzen Zahlen rechnen, solange man ausreichend Speicher hat.

Damit kann man dann die Menge an Primzahlen sicher nochmal vergrößern, allerdings kommt dann auch die Frage, was man mit dieser Liste überhaupt anfangen kann.

Erstaunlich auf jeden Fall, wie mächtig das "alte Sieb" ist.

Ausserdem kann man, falls man aus irgendeinem Grunde gewisse Primzahlen immer wieder neu ermitteln muss, diese in einer Tabelle zwischenspeichern und dann nur die Tabelle durchgehen, das hat damals meine Berechnung wesentlich beschleunigt.

Klar. So eine Tabelle, bzw. Array wird auch schon beim Sieb des Eratosthenes benötigt. Will man möglichst viele Primzahlen berechnen, wird diese Tabelle dann schnell sehr groß, so dass erneut der verfügbare Speicher die Menge an Primzahlen begrenzt.

Damals ging es mir um die Fragestellung, wie viele Primzahlen ich von einer geraden natürlichen Zahl abziehen kann und das Ergebnis ist jedesmal eine Nicht-Primzahl. Also konkret um die Funktion g(n) = kleinste gerade natürliche Zahl, von der man die ersten n Primzahlen subtrahieren kann und das Ergebnis ist eine Nicht-Primzahl.

War das eine Übung, oder gibt es dafür eine weitere Anwendung?

BTW: Die Zahlen 2^n - 1 werden Mersenne-Zahlen genannt und werden bei der Berechnung sehr großer Primzahlen verwendet. Was bieten die Zahlen 2^n + 1? Gibt es dazu keinen effektiven Primzahltest?

**ralfkannenberg** · 09.01.2022, 23:18

Zitat von Bernhard

War das eine Übung, oder gibt es dafür eine weitere Anwendung?

Hallo Bernhard,

hätte ich diese "Übung" gelöst, so hätte ich die Fields-Medaille bekommen. Die Aufgabenstellung ist äquivalent zur Goldbach'schen Vermutung, deswegen auch meine Wortwahl g(x).

Freundliche Grüsse, Ralf

**ralfkannenberg** · 09.01.2022, 23:27

Zitat von Bernhard

Die Zahlen 2^n - 1 werden Mersenne-Zahlen genannt

Hallo zusammen,

hierzu gibt es eine schöne Anekdote über Frank Nelson Cole, die wir im Studium gelernt haben und die auch in der Wikipedia dokumentiert ist:

Im Jahre 1903 präsentierte er bei einem Treffen der American Mathematical Society in einem ungewöhnlichen Vortrag die Faktoren der Mersenne-Zahl 267-1 (kurz M67). Bereits 1876 hatte Édouard Lucas gezeigt, dass diese Zahl, entgegen der Angabe von Marin Mersenne, keine Primzahl ist. Primfaktoren dieser Zahl blieben aber unbekannt.

Bei seinem Vortrag ging Cole wortlos zur Tafel und berechnete den Wert von M67. Sodann schrieb er auf die andere Tafelseite die Aufgabe 193.707.721 · 761.838.257.287. Er führte die langwierige Multiplikation handschriftlich aus und zeigte am Schluss, dass beide Berechnungen zum gleichen Ergebnis von 147.573.952.589.676.412.927 führten. Ohne ein Wort gesprochen zu haben, ging Cole an seinen Platz zurück, während seine Kollegen aufstanden und ihm applaudierten.

Man muss sich das einmal vorstellen: da geht einer zur Tafel, spricht kein Wort und subtrahiert 1 von einer Zweierpotenz.

Danach geht er weiterhin wortlos zur anderen Tafelhälfte und multipliziert dort zwei Zahlen. Das ist übrigens Grundschulmathematik.

Ohne ein Wort gesprochen zu haben erhebt sich die gesamte Zuhörerschaft und spendet standing ovations, denn sie wissen natürlich ganz genau, was Cole in diesem Moment bewiesen hat, und natürlich haben sie schon vorher bereits nach der 1.Zeile geahnt, dass Cole das nun beweisen wird, was er dann auch tat.

Freundliche Grüsse, Ralf

**Bernhard** · 10.01.2022, 08:49

Zitat von ralfkannenberg

was Du hier machen kannst ist Zahlen mit Hilfe zweier Varialen zusammenzusetzen, d.h. die ersten 10 Stellen eines Primzahlkandidaten in einer Variablen und die anderen 10 Stellen in der anderen Variablen.

Hast Du das bei Deinem damaligen "Goldbach-Projekt" verwendet? Falls ja, waren die Zahlen also vermutlich auf 20 Stellen begrenzt.

**Bernhard** · 10.01.2022, 11:24

Zitat von ralfkannenberg

Ausserdem kann man, falls man aus irgendeinem Grunde gewisse Primzahlen immer wieder neu ermitteln muss, diese in einer Tabelle zwischenspeichern und dann nur die Tabelle durchgehen, das hat damals meine Berechnung wesentlich beschleunigt.

Zur Abschätzung der Größe einer solchen (Hilfs-)Tabelle ist wieder die Primzahlfunktion hilfreich.

**Bernhard** · 10.01.2022, 11:29

Zitat von ralfkannenberg

Man muss sich das einmal vorstellen: da geht einer zur Tafel, spricht kein Wort und subtrahiert 1 von einer Zweierpotenz.

Danach geht er weiterhin wortlos zur anderen Tafelhälfte und multipliziert dort zwei Zahlen. Das ist übrigens Grundschulmathematik.

In diesem Vortrag waren sicher fast ausnahmlos echte Zahlenfreunde anwesend.

Die genannte Primfaktor-Zerlegung von M(67) schafft ein kurzes Python-Script heute in maximal einer Minute Rechenzeit.