Das "Sieb des Eratosthenes"

Der griechische Mathematiker Eratosthenes lebte von ca. 275 - 194 vor Christi Geburt. Er hat ein Verfahren zur Bestimmung aller Primzahlen in einem beliebigen Zahlenbereich von 1 bis N gefunden, das seither "Sieb des Eratosthenes" genannt wird. Dieses Verfahren funktioniert so:

Du schreibst dir alle Zahlen von 1 bis N auf. Die 1 kannst du schon gleich durchstreichen, sie ist keine Primzahl. Dann streichst du nach der 2 jede durch 2 teilbare Zahl durch, also alle geraden Zahlen. Weil alle diese Zahlen alle durch 2 teilbar sind, können es keine Primzahlen sein.

Ich führe dir das mal an den Zahlen bis 20 vor: Hier sind die Zahlen von 1 bis 20:

Die Zahl 1 kannst du gleich streichen, sie ist keine Primzahl. Das Durchstreichen von Zahlen geht auf dem Computer schlecht, daher werden alle Zahlen, die keine Primzahl sind, farbig hinterlegt.

Wir fangen dann mit 2 an und streichen nach (!) der 2 alle durch 2 teilbaren Zahlen durch. Die 2 selbst wird nicht angestrichen: Sie ist ja eine Primzahl.

Dann machst du das gleiche mit der 3: streiche alle Zahlen nach der durch, die durch 3 teilbar sind, also: 6, 9, 12, usw. Auch diese Zahlen sind keine Primzahlen (weil sie ja durch 3 teilbar sind). Manche dieser Zahlen hast du schon durchgestrichen, weil es gerade Zahlen (durch 2 teilbar) sind:

Dann suchst du ab der 3 die nächste Zahl, die noch nicht durchgestrichen ist. Diese Zahl ist die nächste Primzahl, nämlich 5. Verfahre weiter wie oben beschrieben, indem du alle Zahlen nach der 5 durchstreichst, wenn sie ein Vielfaches von 5 sind. Hier ist eigentlich nichts mehr zu tun, weil alle Zahlen bis 20, die durch 5 teilbar sind, auch durch 2 oder 3 teilbar sind und somit schon durchgestrichen sind.

Also machst du gleich weiter: Suche ab der 5 die nächste Zahl, die noch nicht durchgestrichen ist: Das ist die 7. Da diese Zahl bei den vorangegangenen Streichaktionen noch nicht durchgestrichen wurde, gibt es keine Zahl kleiner als 7, deren Vielfaches 7 ist. Also ist 7 auch eine Primzahl.

Auch hier bleibt für dich nichts mehr zu tun, denn die 14 ist schon durchgestrichen (sie ist ja ein Vielfaches der 2, nämlich 2 * 7).

Und damit ergibt sich gleich eine weitere, interessante Eigenschaft des "Sieb des Eratosthenes": bei einer beliebigen Zahl N müssen nicht alle Primzahlen überprüft werden, sondern nur die Primzahlen p, bei denen gilt: p * p < N. Wenn N = 20 ist, dann ist dieses p = 3, denn 3 * 3 = 9 < 20, aber bei der nächsten Primzahl 5 gilt schon 5 * 5 = 25 > 20. Warum ist das so?

Wenn du bei dem "Sieb des Eratosthenes" bei der 5 angekommen bist, dann brauchst du ja nicht mehr 2 * 5, 3 * 5, und 4 * 5 zu überprüfen. Diese Zahlen hast du schon gestrichen, als du die Vielfachen der 2 und der 3 gestrichen hast. Also reicht es aus, bei der 5 erst die Zahl 5 * 5 = 25 zu streichen. Da wir aber nur die Primzahlen bis 20 herausbekommen wollten, sind wir schon fertig.

Wenn du nun die Primzahlen bis 100 bestimmen sollst, bis zu welcher Primzahl musst du dann die Vielfachen streichen?

Du siehst also: Es ist garnicht so schwer, alle Primzahlen von 1 bis 100 zu finden!