Sieb des Eratosthenes

Das Sieb des Eratosthenes ist ein Algorithmus, mit dem alle Primzahlen bis zu einer bestimmten Zahl errechnet werden können.

Der Algorithmus wird wie folgt ausgeführt:

Man streiche aus einer mit der Zahl zwei beginnenden Liste natürlicher Zahlen bis zu einem gewünschten Maximalwert alle Vielfachen der ersten Zahl (also der Zwei).
Wähle, solange es noch höhere Zahlen gibt, die nächsthöhere nicht durchgestrichene Zahl und streiche alle ihre Vielfachen.

Die Zahlen, die nach dem Ablauf des Verfahrens übrigbleiben, sind alle Primzahlen bis zum Maximalwert.

Weblinks