MathePrisma Logo

Primzahlgeheimnisse

Primzahlgeheimnisse

Primzahlen

EN

Das Sieb des Eratosthenes bestimmt alle Primzahlen \(\leq\) 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 \(p^{2}\leq N\) gilt: (Abbruchbedingung: \(p^{2}> 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 \(\leq N\) .

Weshalb funktioniert das Sieb?

Die gestrichenen Zahlen sind zusammengesetzt. Wir wollen jetzt überlegen, weshalb alle anderen Zahlen tatsächlich Primzahlen sind.

  1. Die Siebzahlen sind Primzahlen, sonst wären sie bei einer vorangegangenen Siebung gestrichen worden.
  2. 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\leq n:q\), also \(q^{2}\leq n\).
  • Alle zusammengesetzten Zahlen \(n\leq N\) werden also beim Sieben mit einer Siebzahl p mit \(p^{2}\leq 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\leq35:5\), also \(5^{2}\leq 35\).
  • Die zusammengesetzte Zahl 35 wird erstmalig beim Sieben mit der Siebzahl 5 gestrichen.

Abbruchbedingung

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: \(p^{2}> 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?

Antwort:  

Welches ist die größte Siebzahl beim obigen Sieb des Eratostenes (Primzahlen bis 100)?

Antwort:  

Welches ist die größte Siebzahl, wenn man alle Primzahlen bis 1000 aussieben möchte?

Antwort:  

Wieviele Siebzahlen verwendet man dann insgesamt?

Antwort: