Sieb des Eratosthenes

Das Sieb des Eratosthenes ist ein Verfahren (Algorithmus) zur Bestimmung von Primzahlen. Auf dieser Seite wird euch erklärt, wie das Verfahren funktioniert, Ihr könnt euch an Beispielen die Arbeitsweise des Sieb des Eratosthenes vorführen lassen und den hier eingesetzen (Javascript-) Code ansehen oder downloaden.

Primzahlen

Eine natürliche Zahl p, die größer als 1 ist und nur durch 1 und sich selbst teilbar ist, nennt man eine Primzahl. Die ersten fünf Primzahlen sind 2, 3, 5, 7 und 11.

Es gibt zwar unendlich viele dieser Primzahlen, aber leider keine direkte Berechnungsmöglichkeit p(n) = …, um etwa die n-te Primzahl p(n) einfach so auszurechnen.

Eine Möglichkeit zur Bestimmung von Primzahlen ist das Sieb des Eratosthenes. Es handelt sich um einen Algorithmus, der folgendermaßen arbeitet:

Sieb des Eratosthenes

  1. gegeben sei eine natürliche Zahl N > 2,
         erstelle eine Liste mit den Zahlen 2, 3, 4, … , N
     
  2. gehe zur nächsten nicht durchgestrichenen Zahl p in der Liste, ist p2 > N gehe zu Punkt 5
     
  3. gehe nun von p aus weiter durch die gesamte Liste und streiche dabei alle (echten)
         Vielfachen von p durch, also nicht 1·p = p, aber dafür 2·p, 3·p, 4·p usw.
     
  4. gibt es weitere nicht durchgestrichenen Zahlen in der Liste,
         dann führe erneut Punkt 2 aus,
         sonst weiter mit Punkt 5
     
  5. ENDE, die nicht durchgestrichenen Zahlen sind die Primzahlen p mit 2 ≤ p ≤ N
     

Schauen wir uns das Verfahren im Detail an einem Beispiel an:

Beispiel zum Sieb des Eratosthenes

Es sei N = 15.

Unsere Liste lautet:
2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15

Wir gehen zur ersten nicht durch gestrichenen Zahl in der Liste:
2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15

Wir müssen alle echten Vielfachen von 2 streichen, das sind die rot markierten:
2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15

Unsere Liste sieht dann so aus:
2 , 3 , _ , 5 , _ , 7 , _ , 9 , _ , 11 , _ , 13 , _ , 15

Wir gehen jetzt weiter zur 3:
2 , 3 , _ , 5 , _ , 7 , _ , 9 , _ , 11 , _ , 13 , _ , 15

Wir müssen nun alle echten Vielfachen von 3 streichen, das sind wieder die rot markierten:
2 , 3 , _ , 5 , _ , 7 , _ , 9 , _ , 11 , _ , 13 , _ , 15

Unsere Liste sieht jetzt so aus:
2 , 3 , _ , 5 , _ , 7 , _ , _ , _ , 11 , _ , 13 , _ , _

Wir gehen jetzt weiter zur 5:
2 , 3 , _ , 5 , _ , 7 , _ , _ , _ , 11 , _ , 13 , _ , _

Da 52 = 25 größer als 15 ist, können wir keine weiteren Streichungen mehr vornehmen und wir brechen ab.

Die fertige Primzahliste lautet:
2 , 3 , _ , 5 , _ , 7 , _ , _ , _ , 11 , _ , 13 , _ , _

Bemerkung zur Abbruchbedingung

An dem Beispiel erkennt man leicht, dass das Abbruchkriterium p2 > N Sinn macht:

Die Vielfachen 2·5 , 3·5 und 4·5 von p = 5 müssen – falls sie überhaupt in der Liste drin sind – schon gestrichen sein, da die Zahlen 2 , 3 und 4 in unserer Liste vor der 5 drankommen.

Die Vielfachen 5·5 , 6·5 , 7·5 usw. stehen mit Sicherheit gar nicht erst in der Liste drin, da sie alle größer als N = 15 sind und man darf aufhören.

Die Abbruchbedingung hätte übrigens schon früher gegriffen, nämlich bei der Zahl 4. Da aber die 4 keine Primzahl ist, sprich: gestrichen wurde, war sie schon aus dem Spiel bevor die Abbruchbedingung wirken konnte.

Weitere Beispiele zum selber ausprobieren

Bestimme alle Primzahlen ≤


Konkrete Umsetzung des Sieb des Eratosthenes in Code

Im folgenden ist eine Umsetzung des Sieb des Eratosthenes als Javascript-Funktion aufgeführt.

Die Funktion erwartete eine natürliche Zahl N als Eingabe für die Obergrenze. Sie erzeugt eine Liste der Länge N + 1 mit booleschen Werten:

plist[0] = false
plist[1] = false
plist[2] = true
plist[3] = true
…
plist[N] = false oder true

Mit der Liste kann man nun weiterarbeiten, etwa um Primzahl-Listen auszudrucken oder um zu testen, ob eine Zahl eine Primzahl ist. Das könnte z.B. so gehen:

test = SiebVonEratosthenes(500);
if ( test[421] ) document.write(‚412 ist Primzahl.‘); else document.write(‚412 ist keine Primzahl.‘);

function SiebVonEratosthenes(limit)
{
  plist = new Array();
  plist[0] = false;
  plist[1] = false;

  for (i=2; i<=limit; i++) 
    plist[i] = true;

  for (i=2; i*i<=limit; i++)
    if (plist[i]==true)
      for (j=i+1; j<=limit; j++)
        if (j%i==0) plist[j] = false;

  return plist;
}

Sieb des Eratosthenes - Demonstrationsbeispiel auf dieser Seite

Die Javascript-Umsetzung zum Formular auf dieser Seite ist etwas anders aufgebaut, damit Eingabe und Ausgabe benutzerfreundlicher daherkommen.

Der abgedruckte Code ist eine voll funktionstüchtige HTML-Seite mitsamt Formular und Javascript, arbeitet genau wie Formular und Code auf dieser Seite und kann natürlich auch von euch gedownloadet werden.




Sieb des Eratosthenes - Demonstration






  Primzahlen ≤

Auch interessant: