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:

Streiche in einer Liste aller natürlichen Zahlen bis zum Maximalwert und ab zwei, alle Vielfachen der ersten Zahl, 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.

Zum Programmieren kann man folgenden Pseudocode als Anleitung nehmen:

Eratosthenes(n) {

a[1] := 0

for i := 2 to n do a[i] := 1

p := 2

while p2 < n do {

j := 2p

while (j < n) do {

a[j] := 0

j := j+p

}

repeat p := p+1 until a[p] = 1

}

return(a)

}

Link