Primzahlen durch sieben finden.

Wie funktioniert das Sieb des Eratosthenes?

Das Sieb des Eratosthenes ist ein mehr als 2000 Jahre altes Verfahren zur Primzahlsuche in einem Zahlenbereich von 1 bis zu einer wählbaren Obergrenze. Es ist so schnell, weil es keinen Primzahlentest enthält und daher nicht großartig rechnet. Es beschränkt sich auf die Bearbeitung einer Liste.

Man fertigt zuerst eine Liste mit der Größe der Obergrenze an und markiert darin alle Felder als 'ist Primzahl'. Jedes Feld dieser Liste steht für ihre Indexzahl. Da hier mit C#, und daher mit 0 basierten Listen, gearbeitet wird, werden die ersten beiden Elemente als 'ist keine Primzahl' markiert. 0 und 1 sind nicht prim. Mit dem Index 2 beginnend bis zur Wurzel der Obergrenze, wird die Markierung 'ist Primzahl' geprüft. Falls dem so ist, werden alle Zellen mit dem ganzzahligem Vielfachen des soeben geprüften Indexes auf den Wert 'ist keine Primzahl' gesetzt. Andernfalls knöpft man sich die nächste Zelle vor und verfährt ebenso mit ihr. Das Programm sucht alle Primzahlen von 1 bis 2147483647.

Muß ich alle Vielfachen einer Zahl als 'ist keine Primzahl' markieren?

Nein, wenn die Streichschleife rückwärts läuft, reicht es, den Bereich von Obergrenze/aktuellePrimzahl bis aktuellePrimzahl zu bearbeiten.

Was jetzt?

Jetzt kann man nochmal durch die Liste der markierten Zahlen laufen und jeden Index mit einer als 'ist Primzahl' markierten Zelle ausgeben oder in eine Liste schreiben. Nach Adrien-Marie Legendre ist die Anzahl der Primzahlen bis zu einer Obergrenze ca. Obergrenze / (ln(Obergrenze) - 1.08366). Man hat also eine Idee von der ungefähren Listengröße.

Quelltext ein-/ausblenden