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.0Was bedeutet das?