Primzahlen mit dem Sieb des Eratosthenes finden
Finde und zähle alle Primzahlen bis zu einer frei gewählten ganzen Grenze von höchstens 10.000 mit dem Sieb des Eratosthenes.
Diagramm wird geladen …
Rechenweg
So rechnest du selbst
Streiche für jede Primzahl p \le \sqrt{n} die Vielfachen p^2,\ p^2 + p,\ p^2 + 2p,\ \dots
- Schreib die Zahlen von 2 bis n auf.
- Die 2 bleibt, streiche jede zweite Zahl ab 2^2 = 4. Die nächste stehende Zahl, 3, ist prim: streiche ab 3^2 = 9 jede dritte.
- Mach so weiter mit 5, 7 … – bis zur ersten Primzahl, deren Quadrat größer als n ist.
- Alle Zahlen, die dann noch stehen, sind Primzahlen: bis 100 sind es 25.
Typische Fehler
- Die 1 mitgezählt: Die 1 ist keine Primzahl – bis 10 gibt es 4 Primzahlen (2, 3, 5, 7), nicht 5.
- Die Primzahl selbst gestrichen: Die 3 bleibt stehen – gestrichen werden nur ihre Vielfachen 6, 9, 12 …
- Zu lange gesiebt: Bis 100 reichen 2, 3, 5 und 7 – 11^2 = 121 liegt schon über 100.