Zum Inhalt springen

Sieb des Eratosthenes

aus Wikipedia, der freien Enzyklopädie
Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 24. November 2006 um 16:00 Uhr durch Algotekt (Diskussion | Beiträge) (→Funktionsweise). Sie kann sich erheblich von der aktuellen Version unterscheiden.

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.

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. Es genügt dabei, mit dem Quadrat der Primzahl zu beginnen, da alle kleineren Vielfachen bereits markiert sind. Sobald das Quadrat der Primzahl größer als die Schranke S ist, sind alle Primzahlen kleiner oder gleich S bestimmt: Es sind die nicht markierten Zahlen.

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

Eine zusätzliche, wie ich finde wichtige, Eigenschaft von Primzahlen ist, dass sie bis auf die Zahl '2' alle ungerade sind. Aus diesem Grund streiche ich alle geraden Zahlen, die größer sind als die '2', aus dem Zahlenstrang, beim Auffinden der Primzahlen mit dem 'Sieb des Eratosthenes'. Das macht den Vorgang schon einmal etwas übersichtlicher! Allgemein ausgedrückt, rahmt das Quadrat einer gerade neu gefundenen Primzahl die nächsten unmarkierten Primzahlen ein. Das Quadrat von 3 ist 9 und rahmt die 5 und die 7 ein! Wichtig ist dabei, dass bis zu dem oben erwähnten Maximalwert S alle Vielfache der aktuell gefundenen Primzahlen als nichtprim markiert werden.

2 prim; 3 prim; 5 prim; 7 prim; 9=3*3 np; 11 prim; 13 prim; 15=3*5 np; 17 prim; 19 prim; 21=3*7 np; 23 prim; 25=5*5 np; 27=3*9 np; 29 prim; 31 prim; 33=3*11 np; 35=5*7 np; 37 prim; 39=3*13 np; 41 prim; 43 prim; 45=3*15=5*9 np; 47 prim; 49=7*7 np; 51=3*17 np; 53 prim; 55=5*11 np; 57=3*19 np; 59 prim; 61 prim; 63=3*21=7*9 np; 65=5*13 np; 67 prim;

np=nichtprim

mailto:Michael.Gerdes@Algotekt.de

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.

Implementation

Eine beispielhafte Implementierung des Algorithmus ist unter Primzahltest zu finden.

Literatur

Abgerufen von „https://de.wikipedia.org/w/index.php?title=Sieb_des_Eratosthenes&oldid=24229278“