Sieb des Eratosthenes
Verfahren zur Gewinnung von Primzahlen
Basiswissen
a) Man schreibt zunächst eine Liste aller natürlichen Zahlen von der Eins bis zu der höchsten Zahl des zu überprüfenden Bereiches, zum Beispiel:
1;2;3;4;5;6;7;8;9;10;11;12;13,14;15;16;17;18;19;20
b) Nun streicht man als erstes die 1 weg, da es sich bei 1 um keine Primzahl handelt.
c) Es folgt die 2. 2 wurde bis jetzt nicht weggestrichen und ist deshalb Primzahl. Man markiert die 2 als Primzahl.
d) Nun streich ma alle durch 2 teilbaren Zahlen, weil diese nicht Primzahlen sein können. (Sie hätten jeweils die Teiler 1, 2 und sich selbst)
e) Die 3 ist nun die nächste ungestrichene Zahl! Diese wird als Primzahl markiert.
f) Nun streicht man alle durch 3 teilbaren Zahlen, weil diese ebenfalls keine Primzahlen mehr sein können.
g) Man setzt dieses Vorgehen weiter fort bis alle Zahlen entweder als Primzahlen markiert, bzw. als Nichtprimzahlen durchgestrichen sind.
Man erhält in dem Beispiel oben nun eine Liste von Primzahlen: 2, 3, 5, 7, 11, 13, 17 und 19.