Sieb des Eratosthenes

Mit dem Sieb des ERATOSTHENES kann man alle Primzahlen ermitteln, die kleiner als eine vorgegebene natürliche Zahl n sind:

1. Man schreibe alle natürlichen Zahlen von 2 bis n auf.
2. Man markiere die 2 und streiche jede zweite auf 2 folgende Zahl.
3. Ist p die erste nichtgestrichene und nichtmarkierte Zahl, dann markiere man p und streiche jede p-te darauffolgende Zahl.
4. Man führe Schritt c) für alle p mit aus und beende den Algorithmus.

Alle markierten bzw. nicht gestrichenen Zahlen sind Primzahlen. Es handelt sich dabei um alle Primzahlen
In der Menge der ganzen Zahlen werden die Primzahlen und die zu diesen entgegengesetzten Zahlen Primelemente genannt.