Sieb des Eratosthenes
Du bist neugierig, was das Sieb des Eratosthenes ist und wie es dir helfen kann, Primzahlen zu finden? Hier im Beitrag und in unserem Video erfährst du alles, was du dazu wissen musst!
Inhaltsübersicht
Das Sieb des Eratosthenes einfach erklärt
Primzahlen sind besondere Zahlen, die nur durch 1 und sich selbst teilbar sind, wie zum Beispiel 2, 3, 5 oder 7. Doch sie zu finden ist nicht immer leicht, besonders wenn es sehr große Zahlen sind. Genau hier kommt das Sieb des Eratosthenes ins Spiel!
Und so funktioniert es: Zuerst schreibst du alle natürlichen Zahlen von 2 bis zu der Zahl, die du untersuchen willst, auf. Die 1 streichst du gleich weg, weil sie keine Primzahl ist. Nun beginnt das „Sieben“: Du streichst alle Vielfachen von 2 (außer die 2 selbst), dann alle Vielfachen von 3 (außer die 3 selbst), und so weiter. Die Zahlen, die am Ende nicht durchgestrichen sind, sind die Primzahlen!
Das Tolle an dieser Methode ist, dass sie einfach und trotzdem sehr effektiv ist. Du brauchst nur ein Blatt Papier und einen Stift, und schon kannst du selbst Primzahlen finden.
Anwendung vom Sieb des Eratosthenes
Beginnen wir mit einem einfachen Beispiel: Du möchtest alle Primzahlen bis zur Zahl 100 finden. Dafür gehst du wie folgt vor:
Schritt 1: Schreibe die Zahlen auf. Zuerst schreibst du alle Zahlen von 1 bis 100 in einer Reihe auf dein Blatt. Schreibe jeweils 10 Zahlen in eine Reihe und beginne dann die nächste.
Schritt 2: Streiche die Vielfachen von 2. Die 2 ist eine Primzahl, also bleibt sie stehen. Aber jede andere gerade Zahl ist ein Vielfaches von 2. Streiche also alle geraden Zahlen (4, 6, 8, 10, … bis 100).
Schritt 3: Streiche die Vielfachen von 3. Als Nächstes betrachtest du die 3, weil sie die nächste nicht durchgestrichene Zahl in der Liste ist. Streiche alle Vielfachen von 3, die noch nicht gestrichen wurden (9, 15, … bis 99).
Schritt 4: Streiche die Vielfachen von 5. Die nächste nicht durchgestrichene Zahl in der Liste ist die 5. Streiche alle ihre Vielfachen, die noch nicht gestrichen wurden (25, 40 … bis 100).
Schritt 5: Streiche die Vielfachen von 7. Als Nächstes schaust du dir die 7 an. Streiche alle ihre Vielfachen, die noch nicht gestrichen wurden (49, 77, …).
Schritt 6: Weitermachen mit den nächsten Zahlen. Fahre fort mit den übrigen Zahlen (11, 13, 17, …). Bei jeder Zahl streichst du die Vielfachen, die noch nicht gestrichen wurden. Da die meisten Vielfachen aber durch die vorherigen Schritte schon gestrichen wurden, geht der letzte Schritt viel schneller.
Am Ende bleiben die Primzahlen ungestrichen zurück. Diese sind bis zur Zahl 100: 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.
Jetzt hast du eine Liste aller Primzahlen bis 100!
Sieb des Eratosthenes — häufigste Fragen
-
Wie funktioniert das Sieb des Eratosthenes?
Das Sieb des Eratosthenes ist ein antiker Algorithmus, benannt nach dem griechischen Mathematiker Eratosthenes von Kyrene. Er wird zur Identifizierung aller Primzahlen bis zu einer vorgegebenen Obergrenze genutzt.
-
Was sind Primzahlen bis 200?
Primzahlen bis 200 sind alle natürlichen Zahlen größer als 1, die nur durch sich selbst und 1 ohne Rest teilbar sind, wie 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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197 und 199.
Primzahlen
Nun verstehst du, wie das Sieb des Eratosthenes funktioniert. Wenn du mehr über Primzahlen erfahren möchtest, findest du im Beitrag alles Wichtige dazu.
