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 in einer Liste aller natürlichen Zahlen von der Zahl zwei beginnend bis zu dem 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.

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