Sieb des Eratosthenes

Grundidee und Zweck

Das Sieb des Eratosthenes ist ein Algorithmus, mit dem alle Primzahlen bis zu einer vorgegebenen Schranke S bestimmt werden. Eine Primzahl ist eine natürliche Zahl größer als 1, die nur durch 1 und sich selbst teilbar ist. Zusammengesetzte Zahlen besitzen dagegen mindestens einen weiteren Teiler beziehungsweise mindestens einen Primfaktor.

Das Verfahren ist ein einfaches Beispiel für die in der analytischen Zahlentheorie verwendete Siebtheorie. Sein Grundprinzip besteht darin, zunächst alle Zahlen als mögliche Primzahlen zu betrachten und anschließend systematisch die Vielfachen bereits gefundener Primzahlen zu markieren. Die nicht markierten Zahlen sind am Ende genau die Primzahlen bis S.

Das Verfahren ist nach Eratosthenes benannt, einem griechischen Mathematiker des 3. Jahrhunderts v. Chr. Er entdeckte es allerdings nicht, sondern führte nur die Bezeichnung „Sieb“ für ein bereits bekanntes Verfahren ein.

Funktionsweise des Basisverfahrens

Zunächst schreibt man alle Zahlen von 2 bis zu einem frei wählbaren Maximalwert S auf. Zu Beginn ist keine Zahl markiert. Die kleinste unmarkierte Zahl muss eine Primzahl sein: Wäre sie durch eine kleinere Zahl teilbar, wäre sie bereits als Vielfaches einer zuvor gefundenen Primzahl markiert worden.

Für jede gefundene Primzahl werden anschließend alle ihre Vielfachen als zusammengesetzt markiert. Danach sucht man die nächstgrößere unmarkierte Zahl. Auch sie ist prim, weil sie kein Vielfaches einer kleineren Zahl sein kann. Man gibt sie als Primzahl aus, markiert wieder ihre Vielfachen und setzt das Verfahren fort.

Es genügt, nur die Vielfachen von Primzahlen zu streichen, die kleiner oder gleich der Quadratwurzel von S sind. Der Grund ist, dass bei jeder zusammengesetzten Zahl mindestens ein Primfaktor kleiner oder gleich der Quadratwurzel dieser Zahl sein muss. Außerdem beginnt man bei einer Primzahl p erst mit p². Kleinere Vielfache wie 2p, 3p oder allgemein kp mit k < p wurden bereits beim Sieben mit einem kleineren Faktor markiert.

Beispiel für Zahlen bis 120

Um die Primzahlen zwischen 2 und 120 zu bestimmen, werden zunächst alle Vielfachen von 2 gestrichen. Die Markierung beginnt bei 2² = 4. Danach folgt die nächste unmarkierte Zahl 3; ihre Vielfachen werden ab 3² = 9 gestrichen. Anschließend verfährt man ebenso mit 5 und 7, wobei die Markierungen bei 25 beziehungsweise 49 beginnen.

Die nächste Primzahl wäre 11, aber 11² = 121 liegt bereits außerhalb des Wertebereichs bis 120. Deshalb müssen ab 11 keine weiteren zusammengesetzten Zahlen mehr markiert werden. Alle Zahlen, die danach noch unmarkiert sind, sind Primzahlen.

Pseudocode und Optimierungen

Die beispielhafte Implementierung arbeitet mit N = 10000 und einem booleschen Feld gestrichen für die Zahlen von 2 bis N. Zu Beginn werden alle Einträge auf false gesetzt, also als nicht gestrichen gekennzeichnet.

Anschließend wird i von 2 bis sqrt(N) durchlaufen. Ist gestrichen[i] gleich false, ist i prim. Die Zahl wird ausgegeben, und ihre Vielfachen werden in einer inneren Schleife als gestrichen markiert. Diese Schleife beginnt bei ii und erhöht j jeweils um i, also bei ii, ii+i, ii+2i und so weiter.

Nach diesem Durchlauf werden die Zahlen von sqrt(N)+1 bis N untersucht. Jede Zahl, die noch nicht gestrichen wurde, ist prim und wird ausgegeben. Diese abschließende Schleife ist notwendig, weil Primzahlen größer als sqrt(N) selbst nicht als Siebzahlen verwendet werden, aber noch unmarkiert im Feld stehen können.

Eine Optimierung besteht darin, nur bisher nicht markierte Vielfache einer Primzahl zu markieren. Außerdem kann man nur die ungeraden Zahlen speichern, weil alle geraden Zahlen außer 2 zusammengesetzt sind. Allgemeiner können durch ein kleines Produkt von Primzahlen bereits Zahlen ausgeschlossen werden. Im genannten Beispiel besteht jede Zeile aus 10 = 2*5 Einträgen. Vielfache von 2, 4, 5, 6, 8 und 10 müssen in darunterliegenden Zeilen nicht erneut betrachtet werden, weil sie bereits als Vielfache von 2 beziehungsweise 5 nicht als Primzahlen infrage kommen. Diese ausgeschlossenen Vielfachen erscheinen als vertikale Linien.

Es gibt auch effizientere Verfahren als das Sieb des Eratosthenes, beispielsweise das Sieb von Atkin.