|
|
|
Das Sieb des Eratosthenes bestimmt
alle Primzahlen  N,
indem es alle zusammengesetzten Zahlen streicht. Besonders raffiniert
ist dabei das Abbruchkriterium, also die
Entscheidung, wann man den Streichprozess beendet. |
|
|
Das Sieb des Eratosthenes
|
- Schreibe alle natürlichen Zahlen von 2 bis N
auf.
- Setze die Siebzahl p auf 2.
- Solange p2 N
gilt: (Abbruchbedingung: p2>N)
- Siebe mit der Siebzahl p, d.h. streiche jede
p-te Zahl.
- Verwende als neue Siebzahl p die nächste
nicht gestrichene Zahl.
|
Ergebnis
|
Die Siebzahlen und die nicht gestrichenen
Zahlen sind Primzahlen,
und zwar sind dies alle Primzahlen N.
|
|
|
|
|
|
|
Weshalb funktioniert das Sieb?
|
Die gestrichenen Zahlen sind zusammengesetzt.
Wir wollen jetzt überlegen, weshalb alle anderen Zahlen tatsächlich
Primzahlen sind.
- Die Siebzahlen sind Primzahlen, sonst wären sie bei einer
vorangegangenen Siebung gestrichen worden.
- Die anderen nicht gestrichenen Zahlen sind Primzahlen.
Beweis:
- Der kleinste Teiler größer 1 einer zusammengesetzten
Zahl n ist eine Primzahl q.
- Mit q ist auch n:q Teiler von n.
- Weil q der kleinste Teiler ist, gilt q n:q,
also q2 n.
- Alle zusammengesetzten Zahlen n N
werden also beim Sieben mit einer Siebzahl p mit
p2
N gestrichen.
- Die übrigen Zahlen sind also Primzahlen.
Beispiel:
- n = 35 , kleinster Teiler größer 1 ist
die Primzahl q = 5.
- Mit 5 ist auch 35:5 = 7 Teiler von
35.
- Es gilt 5
35:5 , also 52
35.
- Die zusammengesetzte Zahl 35 wird erstmalig beim
Sieben mit der Siebzahl 5 gestrichen.
|
Abbruch-
bedingung
|
Der Beweis zu 2. zeigt, dass man
im Sieb des Eratosthenes mit dem Sieben also tatsächlich dann aufhören
kann, wenn für die Siebzahl p gilt: p2>N
. Diese Beziehung ist also Abbruchbedingung
für die "solange-Schleife". |
|
|
Verstanden?
|
Wie lautet die kleinste zusammengesetzte
Zahl, die nicht die Primteiler 2, 3, 5, 7, aber den Primteiler 11
hat?
|
|
|
|
Welches ist die größte
Siebzahl beim obigen Sieb des Eratostenes (Primzahlen bis 100)?
|
|
|
|
Welches ist die größte
Siebzahl, wenn man alle Primzahlen bis 1000 aussieben möchte?
|
|
|
|
Wieviele Siebzahlen verwendet
man dann insgesamt?
|
|
|
