Mit Google fortfahren
Sieb des Eratosthenes: Primzahlen finden
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.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Primzahlen und die Siebidee
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\cdot4$ 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.
So siebst du bis 100
Schreibe die Zahlen von 2 bis 100 auf. Gehe dann immer gleich vor:
- Nimm die kleinste noch ungestrichene Zahl. Sie ist prim.
- Markiere sie als Primzahl.
- Streiche ihre echten Vielfachen, also die größeren Vielfachen.
- Wiederhole das Verfahren mit der nächsten ungestrichenen Zahl.
Zuerst bleibt 2 stehen. Streiche $4,6,8,10,\ldots,100$.
Die nächste ungestrichene Zahl ist 3. Streiche ihre noch freien Vielfachen $9,15,21,\ldots,99$.
Danach folgen 5 und 7. Bei 5 beginnst du mit 25, bei 7 mit 49. Nach der Runde mit 7 ist das Sieb bis 100 fertig.
Die Primzahlen bis 100 sind:
$2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97$.
Wähle in jeder Lücke die passende Form und prüfe anschließend deine Antworten.
Beim Sieben bis 30 ist die erste ausgewählte Zahl . Danach ist die kleinste ungestrichene Zahl . Die Zahl 25 wird als Vielfaches von gestrichen. Die ungestrichene Zahl 29 ist .
Warum du bei der Quadratzahl beginnst
Bei einer Primzahl $p$ musst du nicht noch einmal alle Vielfachen von vorne prüfen. Beginne die neue Streichrunde bei $p^2$.
Warum? Jedes kleinere Vielfache von $p$ hat die Form $p\cdot k$ mit $k\lt p$. Es wurde bereits in der Runde zu einem kleineren Faktor gestrichen.
In der 5er-Runde liegen $10=5\cdot2$, $15=5\cdot3$ und $20=5\cdot4$ vor $5^2=25$. Sie wurden schon in der 2er- oder 3er-Runde gestrichen. Die erste neue Zahl ist deshalb 25.
Für eine neue Primzahl $p$ beginnt die Streichrunde bei $p^2$ und geht in Schritten von $p$ weiter.
Wann du aufhören kannst
Für eine Grenze $S$ genügt es, mit Primzahlen $p$ zu sieben, solange $p^2\leq S$ gilt. Sobald die nächste ungestrichene Zahl ein Quadrat größer als $S$ hat, ist keine neue Streichrunde nötig.
Für $S=100$ gilt $7^2=49\leq100$, aber $11^2=121\gt100$. Deshalb ist 7 die letzte Primzahl, deren Vielfache du streichen musst. 11 und die weiteren ungestrichenen Zahlen bleiben als Primzahlen stehen.
Das funktioniert, weil jede zusammengesetzte Zahl bis $S$ mindestens einen Primfaktor besitzt, der nicht größer als ihre Quadratwurzel ist. Hätte sie nur größere Faktoren, wäre schon das Produkt zweier solcher Faktoren größer als $S$.
Warum das Verfahren zuverlässig ist
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. Sie besitzt einen Primfaktor, der höchstens so groß wie ihre Quadratwurzel ist. Spätestens in der Runde dieses Primfaktors wird sie erfasst.
Das Sieb erzeugt eine vollständige Primzahlliste nur bis zur gewählten endlichen Grenze. Für sehr große Grenzen ist das einfache Verfahren aufwendig, auch wenn Quadratstart und Abbruchregel unnötige Schritte vermeiden.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Sieb des Eratosthenes
- Vorbereitung
- Zahlen ab 2 bis zur Grenze
- 1 ist keine Primzahl
- Siebschritt
- kleinste ungestrichene Zahl ist prim
- Vielfache ab ihrer Quadratzahl streichen
- Abbruch
- nur solange $p^2$ höchstens die Grenze ist
- Ergebnis
- ungestrichene Zahlen sind Primzahlen
- Vorbereitung