Sieb des Eratosthenes - LinkFang.de





Sieb des Eratosthenes


Das Sieb des Eratosthenes ist ein Algorithmus zur Bestimmung einer Liste oder Tabelle aller Primzahlen kleiner oder gleich einer vorgegebenen Zahl. Er ist nach dem griechischen Mathematiker Eratosthenes von Kyrene benannt. Allerdings hat Eratosthenes, der im 3. Jahrhundert v. Chr. lebte, das Verfahren nicht entdeckt, sondern nur die Bezeichnung „Sieb“ für das schon lange vor seiner Zeit bekannte Verfahren eingeführt.

Funktionsweise

Zunächst werden alle Zahlen 2, 3, 4,… bis zu einem frei wählbaren Maximalwert S aufgeschrieben. Die zunächst unmarkierten Zahlen sind potentielle Primzahlen. Die kleinste unmarkierte Zahl ist immer eine Primzahl. Nachdem eine Primzahl gefunden wurde, werden alle Vielfachen dieser Primzahl als zusammengesetzt markiert. Man bestimmt die nächstgrößere nicht markierte Zahl. Da sie kein Vielfaches von Zahlen kleiner als sie selbst ist (sonst wäre sie markiert worden), kann sie nur durch eins und sich selbst teilbar sein. Folglich muss es sich um eine Primzahl handeln. Diese wird dementsprechend als Primzahl ausgegeben. Man streicht wieder alle Vielfachen und führt das Verfahren fort, bis man am Ende der Liste angekommen ist. Im Verlauf des Verfahrens werden alle Primzahlen ausgegeben.

Da mindestens ein Primfaktor einer zusammengesetzten Zahl immer kleiner gleich der Wurzel der Zahl sein muss, ist es ausreichend, nur die Vielfachen von Zahlen zu streichen, die kleiner oder gleich der Wurzel der Schranke S sind.

Ebenso genügt es beim Streichen der Vielfachen, mit dem Quadrat der Primzahl zu beginnen, da alle kleineren Vielfachen bereits markiert sind.

Das Verfahren beginnt also damit, die Vielfachen 4, 6, 8,… der kleinsten Primzahl 2 durchzustreichen. Die nächste unmarkierte Zahl ist die nächstgrößere Primzahl, die 3. Anschließend werden deren Vielfache 9, 12, 15,… durchgestrichen, und so weiter.

Demonstration

Verfahren, wie die Primzahlen zwischen 2 und 120 ermittelt werden: Erst werden alle Vielfachen von 2 gestrichen, dann alle Vielfachen von 3, 5, und 7. Die Markierungen beginnen jeweils mit dem Quadrat der Primzahl: 4, 9, 25, 49. Da bereits 112 = 121 nicht mehr im Wertebereich liegt, werden ab 11 keine zusammengesetzten Zahlen mehr markiert; alle noch unmarkierten Zahlen sind prim.

Implementierung

Eine beispielhafte Implementierung des Algorithmus als Pseudocode:

 const N = 10000
 var gestrichen: array [2..N] of boolean
 
 // Initialisierung des Primzahlfeldes
 // Alle Zahlen im Feld sind zu Beginn nicht gestrichen
 for i = 2 to N do
     gestrichen[i] = false
 end
 
 // Siebe mit allen (Prim-) Zahlen i, wobei i der kleinste Primfaktor einer zusammengesetzten
 // Zahl j = i*k ist. Der kleinste Primfaktor einer zusammengesetzten Zahl j kann nicht größer
 // als die Wurzel von j <= n sein.
 for i = 2 to sqrt(N) do
     if not gestrichen[i] then
         // i ist prim, gib i aus...
         print i; ", ";
         // ...und streiche seine Vielfachen, beginnend mit i*i
         // (denn k*i mit k<i wurde schon als Vielfaches von k gestrichen)
         for j = i*i to N step i do
             gestrichen[j] = true
         end
     end if
 end
 // Gib die Primzahlen größer als Wurzel(n) aus - also die, die noch nicht gestrichen wurden   
 for i = sqrt(N)+1 to N do
     if not gestrichen[i] then
         // i ist prim, gib i aus
         print i; ", ";
     end if
 end

Das Verfahren lässt sich optimieren, wenn nur die ungeraden Zahlen darin abgespeichert werden. Generell kann man zu einem (kleinen) Produkt von (Prim)zahlen die möglichen Primzahlen bestimmen. Das Sieben muss dann nur auf das Vielfache dieser Zahlen angewendet werden. Im Beispiel besteht jede Zeile aus 10 = 2*5 Einträgen. Man kann erkennen, dass die Vielfachen von 2,4,5,6,8,10 in den darunter liegenden Zeilen nicht betrachtet werden müssen, da sie als Vielfache von 2 bzw. 5 nicht als Primzahlen in Fragen kommen. Diese Vielfachen sind als vertikale Linien erkennbar. Es gibt zwar bessere Verfahren als das Sieb des Eratosthenes (z. B. das Sieb von Atkin), das hier erwähnte ist allerdings immer noch optimal, wenn größere Zahlenbereiche nach Primzahlen abgesucht werden sollen.

Literatur

Weblinks


Kategorien: Zahlentheoretischer Algorithmus | Primzahl

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Sieb des Eratosthenes (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.