Sieb des Eratosthenes: Primzahlen finden
Mit dem Sieb des Eratosthenes findest du alle Primzahlen bis zu einer Grenze. Du lernst die Streichrunden, die Quadratregel und wann du aufhören kannst.
Kurz gesagt
Das Sieb des Eratosthenes ist ein Verfahren, um alle Primzahlen bis zu einer Grenze zu finden. Du schreibst die Zahlen ab 2 auf, nimmst die kleinste ungestrichene Zahl als Primzahl und streichst ihre Vielfachen ab ihrem Quadrat. Bis 100 reichen die Runden mit 2, 3, 5 und 7.
Mit dem Sieb des Eratosthenes findest du alle Primzahlen bis zu einer gewählten Grenze. Du schreibst die Zahlen ab 2 auf und streichst systematisch die zusammengesetzten Zahlen. Übrig bleiben genau die Primzahlen.
Deine Lernziele
Eine Primzahl ist eine natürliche Zahl größer als 1 mit genau zwei verschiedenen Teilern: 1 und sich selbst. Zum Beispiel hat 7 nur die Teiler 1 und 7. Die Zahl 1 ist keine Primzahl, denn sie hat nur einen Teiler. Eine Zahl größer als 1, die keine Primzahl ist, heißt zusammengesetzt. So ist 12 = 3 · 4 zusammengesetzt. Das Sieb streicht solche Zahlen als Vielfache kleinerer Primzahlen.
Sieb des Eratosthenes
Ein Verfahren, das aus einer endlichen Zahlenliste alle zusammengesetzten Zahlen aussortiert. Die ungestrichenen Zahlen sind die Primzahlen der Liste.
Teste dich
Schreibe die Zahlen von 2 bis 100 auf. Dann gehst du immer gleich vor: Die kleinste noch ungestrichene Zahl ist prim. Markiere sie und streiche ihre echten Vielfachen, also die größeren Vielfachen. Dann machst du mit der nächsten ungestrichenen Zahl weiter. Am Ende bleiben 25 Primzahlen stehen: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 und 97.
Beispiel: Die Streichrunden bis 100
- 12 bleibt stehen: streiche 4, 6, 8, 10, …, 100
- 23 bleibt stehen: streiche die noch freien Vielfachen 9, 15, 21, …, 99
- 35 bleibt stehen: streiche ab 25
- 47 bleibt stehen: streiche ab 49
- 5Nach der 7er-Runde ist das Sieb bis 100 fertig.
Teste dich
Bei einer Primzahl musst du nicht alle Vielfachen von vorn prüfen. Nimm die 5: Die Vielfachen 10 = 5 · 2, 15 = 5 · 3 und 20 = 5 · 4 haben einen kleineren Faktor und sind in einer früheren Runde schon gestrichen. Neu ist erst 5 · 5 = 25. Deshalb beginnt eine Streichrunde bei der Quadratzahl der Primzahl.
Auch das Ende ist klar: Du brauchst nur Primzahlen, deren Quadratzahl höchstens so groß ist wie die Grenze. Eine zusammengesetzte Zahl lässt sich als Produkt zweier Faktoren schreiben. Wäre jeder der beiden Faktoren mal sich selbst schon größer als die Grenze, dann wäre auch ihr Produkt größer als die Grenze. Jede zusammengesetzte Zahl bis zur Grenze hat also einen Faktor, dessen Quadratzahl höchstens die Grenze ist.
Beispiel: Start der 3er-Runde
- 16 = 3 · 2 ist schon in der 2er-Runde gestrichen.
- 2Die erste neue Zahl ist 3 · 3 = 9.
- 3Danach geht es in Dreierschritten weiter: 9, 12, 15, 18, …
Beispiel: Ende beim Sieben bis 100
- 17 · 7 = 49 ist höchstens 100: Die 7er-Runde ist nötig.
- 211 · 11 = 121 ist größer als 100: Eine 11er-Runde brauchst du nicht mehr.
- 3Alle ungestrichenen Zahlen sind jetzt Primzahlen.
Merke: Die Streichrunde einer neuen Primzahl beginnt bei ihrer Quadratzahl und geht in Schritten dieser Primzahl weiter.
Teste dich
Die jeweils kleinste ungestrichene Zahl kann kein Vielfaches einer kleineren Primzahl sein: Sonst wäre sie in einer früheren Runde gestrichen worden. Sie hat also keinen Teiler zwischen 1 und sich selbst und ist prim. Umgekehrt wird jede zusammengesetzte Zahl bis zur Grenze gestrichen. Ihr kleinster Primfaktor ist so klein, dass seine Quadratzahl höchstens die Zahl selbst ist. Spätestens in der Runde dieses Primfaktors wird sie erfasst. Das Sieb liefert eine vollständige Primzahlliste nur bis zur gewählten Grenze. Für sehr große Grenzen wird es mühsam, auch wenn Quadratstart und Abbruchregel unnötige Schritte sparen.
Beispiel: Warum 95 gestrichen wird
- 195 = 5 · 19, der kleinste Primfaktor ist 5.
- 25 · 5 = 25 ist kleiner als 95.
- 3Also wird 95 in der 5er-Runde gestrichen.
Teste dich
Alles auf einen Blick
Sieb des Eratosthenes
genau zwei Teiler, 1 und sich selbst
Zahlen ab 2 bis zur Grenze; 1 ist keine Primzahl
kleinste ungestrichene Zahl ist prim; Vielfache ab ihrer Quadratzahl streichen
nur solange die Quadratzahl der Siebzahl höchstens die Grenze ist
ungestrichene Zahlen sind Primzahlen
Alle Primzahlen bis 50 finden
- 1Zahlen von 2 bis 50 aufschreiben
- 22 bleibt, streiche 4, 6, 8, …, 50
- 33 bleibt, streiche ab 3 · 3 = 9: 9, 15, 21, …, 45
- 45 bleibt, streiche ab 5 · 5 = 25: 25 und 35
- 57 bleibt, streiche ab 7 · 7 = 49: nur 49
- 6Nächste Zahl 11: 11 · 11 = 121 ist größer als 50, fertig
- 7Primzahlen: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
Fehler finden
Fehler in Zeile 4Die 7er-Runde beginnt erst bei 7 · 7 = 49, und 49 ist höchstens 60. Sie ist also nötig und streicht 49 = 7 · 7. Aufhören darfst du erst bei 11, denn 11 · 11 = 121 ist größer als 60.
Lückentext
Beim Sieben bis 30 ist die erste ausgewählte Zahl . Danach ist die kleinste ungestrichene Zahl . Die Zahl 25 wird als Vielfaches von gestrichen.