Größere Schriftzeichen   

Sieb des Eratosthenes:

Um eine Liste von Primzahlen zu erzeugen, kann folgende, auf Eratosthenes von Kyrene zurückgehende Methode verwendet werden:

Schreiben wir zunächst alle natürlichen Zahlen zwischen 2 und einer vorgegebenen Maximalzahl (in diesem Beispiel 20) auf:

 2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20 

Die Liste beginnt mit 2, welches auch die erste Primzahl ist. Alle Vielfachen von 2 (d.h. alle geraden natürlichen Zahlen) haben 2 als Teiler, sind daher keine Primzahlen. Wir streichen sie durch und heben 2 hervor:

 2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20 

Die nächste Zahl nach 2, die nicht durchgestrichen ist, ist 3, die zweite Primzahl. Wir heben sie hervor und streichen ihre Vielfachen (6,9,12,...) durch (wobei die geraden unter ihnen, wie z.B. 6, bereits durchgestrichen sind):

 2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20 

Die nächste Zahl nach 3, die nicht durchgestrichen ist, ist 5 - wieder eine Primzahl, da sie nicht Vielfaches einer kleineren Zahl ist (ansonsten wäre sie ja durchgestrichen)! Wir heben sie hervor und streichen ihre Vielfachen (10,15,...) durch. Dieses Verfahren wird solange angewandt, bis alle Zahlen in der Liste entweder hervorgehoben (also Primzahlen) oder durchgestrichen (also keine Primzahlen) sind. In unserem Beispiel kommen keine neuen Streichungen hinzu (alle zu streichenden Zahlen sind bereits durchgestrichen), und wir erhalten:

 2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20 

Daraus können wir die Primzahlen 2, 3, 5, 7, 11, 13, 17, 19 ablesen.

Die Methode ist natürlich in der Lage, längere Listen zu erzeugen. Sie ''siebt'' die Primzahlen systematisch aus, daher ihr Name. Ihr Nachteil ist, daß es erheblichen Aufwand erfordert, große Primzahlen zu finden oder von einer Zahl wie 104729 zu entscheiden, ob sie Primzahl ist.(104729 ist die zehntausendste Primzahl!) Es gibt zwar effektivere Methoden zur Erzeugung oder Bestätigung großer Primzahlen, aber kein wirklich einfaches Schema.