Schlagwort-Archive: eratosthenes

Es gibt 25 Primzahlen kleiner 100.

Die Primzahlen bis 100 sind: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 und 97.

Sie können mit dem Sieb des Eratosthenes bestimmt werden.

Primzahlen bis 100 mit dem Sieb des Eratosthenes

Schreiben Sie zunächst die Zahlen bis 100 auf. Eins ist nicht prim und kann direkt gestrichen werden.

Vielfache müssen nur für Primzahlen bis zur Wurzel von 100, also bis 10, gestrichen werden.

Die erste ungestrichene Zahl ist 2. Streichen Sie alle Vielfachen von 2, beginnend mit der Quadratzahl von 2: 4. Streichen Sie also: 4, 6, 8, 10, …, 96, 98, 100

Die nächste ungestrichene Zahl ist 3. Streichen Sie alle Vielfachen von 3, beginnend mit der Quadratzahl von 3: 9. Streichen Sie also: 9, 12, 15, 18, …, 93, 96, 99

Die nächste ungestrichene Zahl ist 5. Streichen Sie alle Vielfachen von 5, beginnend mit der Quadradzahl von 5: 25. Sie streichen: 25, 30, 35, …, 90, 95, 100

Die nächste ungestrichene Zahl ist 7. Wieder streichen Sie alle Vielfachen von 7, beginnend mit der Quadradzahl von 7: 49. Gestrichen werden: 49, 56, 63, …, 84, 91, 98

Da die nächste ungestrichene Zahl 11 größer als 10 ist, sind die Streichungen beendet und Sie können die Primzahlen ablesen. Alle nicht gestrichenen Zahlen sind prim.

Sie haben die Primzahlen bis 100 bestimmt:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Das nach Eratosthenes von Kyrene (ca. 275 v. Chr. – ca. 194 v. Chr.) als Sieb des Eratosthenes benannte Verfahren dient der Bestimmung der Primzahlen bis zu einer beliebigen Grenze. Das Verfahren war schon lange vor Eratosthenes bekannt. Der vielseitige Gelehrte prägte jedoch den Begriff Sieb.
Wie funktioniert das Sieb des Eratosthenes?
Das Verfahren funktioniert so, dass man aus dem betrachteten Zahlenbereich alle Zahlen streicht, die keine Primzahlen sein können.

Übrig bleiben die Primzahlen im Zahlenbereich.

Dabei nutzt man die Bedingung für Primzahlen aus, dass eine Primzahl nur durch 1 und durch sich selbst teilbar ist. Eine Primzahl ist somit kein Vielfaches einer anderen Zahl, denn sonst wäre diese andere Zahl ja auch ein Teiler.
Anleitung für das Sieb des Eratosthenes
Schreiben Sie also alle Zahlen im betrachteten Zahlenbereich auf. Eins ist nicht prim und kann gestrichen werden.

Nun nehmen Sie jeweils die nächste noch nicht gestrichene Zahl – sie ist eine Primzahl, weil sie kein Vielfaches einer anderen ist.

Streichen Sie alle ihre Vielfachen, da diese nicht prim sein können.

Dies wiederholen Sie so lange, bis der Zahlenbereich erschöpft ist.
Optimierung des Sieb des Eratosthenes?
Zwei Beobachtungen beschleunigen das Verfahren deutlich:

1. Mit den Streichungen der Vielfachen kann bei der Quadratzahl begonnen werden, da alle kleineren Vielfachen bereits durch vorhergehende Primzahlen abgedeckt sind.
2. Die Streichungen selbst müssen nur bei Zahlen durchgeführt werden, die kleiner oder gleich der Wurzel der Zahl sind, die den Zahlenbereich begrenzt, da Primfaktoren einer zusammengesetzten Zahl immer kleiner oder gleich ihrer Wurzel sind.

Beispiel zum Sieb des Eratosthenes
Als beispielhafte Anwendung des Sieb des Eratosthenes bestimmen Sie mit ihm die Primzahlen bis 100.