Sieb des Eratosthenes

Das Sieb des Eratosthenes ist ein Verfahren, in dem durch Überprüfung aller natürlichen Zahlen auf Primalität bis zu einer vorgegebenen Zahl n (inklusive n), alle Primzahlen gefunden werden.
Ablauf des Sieb des Erathostenes:

  1. Es werden alle natürlichen Zahlen von 2 bis n hintereinander aufgeschrieben.
  2. Nun werden die natürlichen Zahlen nacheinander durchgegangen und dabei die echten Vielfachen der aktuellen Zahl gestrichen. Ist eine Zahl schon gestrichen, wird mit der nächstgrößeren Zahl fortgefahren.
    1. 2: gestrichen wird: 4, 6, 8, 10, 12, …
    2. 3: gestrichen wird: 6 (ist schon gestrichen), 9, 12 (ist schon gestrichen), 15, 18 (ist schon gestrichen), …
    3. 4: ist schon gestrichen, also sind auch schon alle Vielfachen gestrichen
    4. 5: gestrichen wird: 5, 10 (ist schon gestrichen), 15, 20 (ist schon gestrichen), 25, …
    5. 6: …
  3. Beim Streichen der Zahlen gibt es zwei Vereinfachungen:

    • Es ist ausreichend, nur die Vielfachen von Zahlen zu streichen, die kleiner oder gleich der Wurzel der vorgegebenen Zahl n sind. (Weil bei zusammengesetzten Zahlen mindestens ein Primfaktor immer kleiner gleich der Wurzel aus dieser Zahl ist).
    • Es ist ebenso ausreichend beim Streichen mit dem Quadrat der aktuellen Zahl zu beginnen, da alle anderen kleineren Vielfachen bereits gestrichen sind.

    Übungen und Lösungen zum Sieb des Eratosthenes

    Hier finden Sie Übungsblätter und deren Lösungen zum Download, auf denen das Sieb des Eratosthenes behandelt wird.
    Auf den Übungsblättern ist die Vorgehensweise zur Lösung erklärt.

    Im ersten Übungsblatt werden die Zahlen bis 50 behandelt:
    Übung - Sieb des Eratosthenes - Primzahlen bis 50
    Lösung - Sieb des Eratosthenes - Primzahlen bis 50

    Weitere und ähnliche Verfahren zum Sieb des Eratosthenes

    Eine moderne Variante des Eratosthenes-Siebes ist das Sieb von Atkin.