Sieb des Eratosthenes

Das Sieb des Eratosthenes ist ein Hilfsmittel zur Findung der Primzahlen. Es ist notwendig, da es keine Formel gibt, um Primzahlen berechnen zu können.

Sieb des Eratosthenes

Bis heute gibt es noch keine Formel zur Ermittlung der Primzahlen. Noch niemand hat eine Regelmäßigkeit in ihrem Auftreten gefunden, deshalb muss man sich andere Hilfsmittel zur Ermittlung der Primzahlen zu Hilfe nehmen.

Eines davon ist das sogenannte Sieb des Eratosthenes, benannt nach dem griechischen Mathematiker Eratosthenes von Kyrene (276 - 194 v. Chr.)

Anleitung:

Man schreibt die Zahlen bis z.B. 100 auf (am übersichtlichsten in Reihen zu je 10 Zahlen). Dann "sieben" wir alle Zahlen aus, die durch eine andere Zahl als 1 oder sich selbst teilbar sind. Jene Zahlen, die übrig bleiben, sind schließlich die Primzahlen.


Schritt 1:

Die Zahl 1 kann gestrichen werden, da sie keine Primzahl ist.


Schritt 2:

Die Zahl 2 wird angemalt, da es sich bei ihr um eine Primzahl handelt.

Alle Vielfachen von 2 sind durch 2 teilbar, sind also keine Primzahlen. Deshalb können wir diese Zahlen durchstreichen (4, 6, 8, 10, ...)


Schritt 3:

Die Zahl 3 wird angemalt, da es sich bei ihr um eine Primzahl handelt.

Alle Vielfachen von 3 sind durch 3 teilbar, sind also keine Primzahlen. Deshalb können wir diese Zahlen durchstreichen (6, 9, 12, ...)


Schritt 4:

Die Zahl 4 ist bereits gestrichen, kann also übersprungen werden.

Die Zahl 5 wird angemalt, da es sich bei ihr um eine Primzahl handelt.

Alle Vielfachen von 5 sind durch 5 teilbar, sind also keine Primzahlen. Deshalb können wir diese Zahlen durchstreichen (10, 15, 20, ...)


Schritt 5:

Die Zahl 6 ist bereits gestrichen, kann also übersprungen werden.

Die Zahl 7 wird angemalt, da es sich bei ihr um eine Primzahl handelt.

Alle Vielfachen von 7 sind durch 7 teilbar, sind also keine Primzahlen. Deshalb können wir diese Zahlen durchstreichen (14, 21, 28, ...)


Schritt 6:

Die restlichen verbleibenden Zahlen können angemalt werden, es handelt sich dabei um die Primzahlen.

Kommentar #8542 von Ronald Hofmann 17.02.14 02:31
Ronald Hofmann

Hallo,
dieses Verfahren ist ganz nett, wenn es um nur wenige Zahlen geht wie in diesem Beispiel. Kompliziert wird es bei vielen Zahlen. Z.B. alle Primzahlen bis 150.000.000. Muss ich mir dann erst ein Array mit allen Zahlen erstellen und dann nach der beschriebenen Methode aussieben? Das dauert lange. Allein das Füllen des Arrays schon. Oder gibt es da eine andere Methode?

Grüsse, Ronald Hofmann
---

Kommentar #9362 von Max Weber 28.10.14 13:23
Max Weber

Hallo,
neben dem Sieb des Eratosthenes gibt es noch eine optimiertere Version davon: das Sieb von Atkin, das mit dem 60er Rest der Zahlen arbeitet und damit einige Vorarbeit leistet. Dieses Verfahren sollte schneller gehen.
Grüße, Max Weber

Kommentar #10214 von Catrina 01.07.15 11:34
Catrina

Bei diesem Beispiel reicht es, wenn man es bis 7 prüft. Nimmt man Zahlen bis 200, was per Hand noch geht, reicht das aber nicht. Allgemeiner formuliert: Zahlen möglichst im Quadrat anordnen (beim Rechteck sollte die waagerechte länger sein, unvollständige Reihen sind ok, zählen aber als Reihe) und dann die Vielfachen der obersten Reihe streichen.

Kommentar #36152 von Sarina 15.02.17 15:46
Sarina

Hallo!Das Sieb des Eratosthenes ist wirklich sehr praktisch.Ich habe da nur noch eine Frage:wieso heißt es eigentlich "Sieb"?

Kommentar #36196 von Erich Hnilica, BEd 16.02.17 13:51
Erich Hnilica, BEd

Liebe Sarina!
Diese Methode wurde nach dem griechischen Mathematiker Eratosthenes von Kyrene benannt.
Sieb deshalb, weil wie mit einem Sieb die Zahlen ausgesiebt werden, bis nur noch die Primzahlen übrig bleiben.
Lg
Admin

Kommentar #43072 von Amelie 29.10.19 16:30
Amelie

Ich finde es gut

Kommentar verfassen