🎓 Ui, fast schon PrĂŒfungszeit? Hier geht's zur Mathe-PrĂŒfungsvorbereitung.
Springe zum Inhalt oder Footer
SerloDie freie Lernplattform

Das Sieb des Eratosthenes

Das Sieb des Eratosthenes ist ein Verfahren, um systematisch alle Primzahlen aus einer Liste von Zahlen zu bestimmen. Diese Liste beginnt mit der Zahl 22 und enthĂ€lt alle darauffolgenden natĂŒrlichen Zahlen bis zu einer festgelegten grĂ¶ĂŸten Zahl. Eins wird nicht betrachtet, weil sie direkt als Primzahl ausgeschlossen werden kann. Man könnte auch sagen, dass mit diesem Verfahren alle Primzahlen der Liste herausgesiebt werden.

Das Verfahren

Um nun alle Primzahlen einer gegebenen Liste zu bestimmen, werden folgende Schritte durchlaufen:

verfahren sieb des eratosthenes
  1. ZunĂ€chst wĂ€hlt man die kleinste Zahl der Liste aus und umkreist sie. Bei der ersten Bearbeitung der Liste wird dabei die Zahl 22 ausgewĂ€hlt. Alle Vielfachen dieser Zahl werden dann in der Liste gestrichen. FĂŒr die Zahl 22 bedeutet dies, dass 44, 66, 88,
 gestrichen werden.

  2. Dann wird die nÀchste noch nicht durchgestrichene Zahl der Liste ausgewÀhlt und umkreist. Dies ist nun die Zahl 33.

  3. FĂŒr die nun ausgewĂ€hlte Zahl werden wie im ersten Verfahrensschritt ihre Vielfachen aus der Liste gestrichen.

  4. Die beschriebene Verfahrensweise wird so lange wiederholt, bis keine zu streichenden Zahlen mehr ĂŒbrig sind.

  5. Das Verfahren ist dann beendet und die umkreisten Zahlen sind alle Primzahlen der Liste.

Beispiel

Idee des Verfahrens

Die Idee des Verfahrens ist es, die Liste auf die Primzahlen zu reduzieren. Die zusammengesetzten Zahlen fallen durch das Sieb und die Primzahlen bleiben zurĂŒck. Zusammengesetzte Zahlen bedeuten in diesem Zusammenhang, dass sich diese Zahlen in Primfaktoren zerlegen lassen.

Bislang gibt es keine Formel, mit der alle existierenden Primzahlen berechnet werden können. Das "Sieb des Eratosthenes" bietet zumindest die Möglichkeit, alle Primzahlen einer endlichen Liste systematisch zu bestimmen.

Vertiefende Aufgabe

Du hast noch nicht genug vom Thema?

Hier findest du noch weitere passende Inhalte zum Thema:

Artikel


Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0 → Was bedeutet das?