Das Sieb des Eratosthenes

Das Sieb des Eratosthenes (griechischer Mathematiker, ca. 275-194 v.Chr.) ist einer der ältesten Algorithmen zur Bestimmung aller Primzahlen innerhalb eines gewissen Intervalls [2;n]. Es ist bis heute das beste Verfahren für diese Aufgabe.

Grundprinzip

Das Sieb des Eratosthenes basiert auf der Eigenschaft, dass jede natürliche Zahl entweder eine Primzahl oder das Vielfache einer solchen ist.

Zunächst werden alle Natürlichen Zahlen des gewünschten Intervalls in einer Liste aufgeschrieben:

Nun werden, bei 2 beginnend, alle Vielfachen der jeweils niedrigsten Zahl aus der Liste gestrichen (Diese können ja keine Primzahlen sein, da sie Vielfache der niedrigsten Zahl sind):

Hat man dieses Verfahren oft genug durchgeführt, so bleiben am Ende nur noch die Primzahlen übrig (diese werden niemals gestrichen, da sie nicht vielfache irgendeiner kleineren Zahl sind):

Optimierung des Prinzips

Dieses Verfahren lässt sich jedoch noch deutlich Optimieren, beachtet man folgende zwei Regeln:

1. Die kleinste Zahl, die als Vielfaches einer Primzahl gestrichen wird ist ihr Quadrat. Alle niedrigeren Vielfache sind bereitsgestrichen, da sie auch Vielfache einer kleineren Primzahl sind.
2. Die größte Zahl deren Vielfache noch gestrichen werden müssen ist die Wurzel der höchsten Zahl des Intervalls, in unserem Beispiel:

Damit sind wir in diesem Beispiel, dem Intervall von 2 bis 50 bereits nach 4 Schritten fertig! Es sind nur die Vielfachen von 2, 3, 5 und 7 zu streichen.