Sieb des Eratosthenes

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.

Basisverfahren: Es werden alle Vielfachen einer Primzahl markiert, die größer oder gleich deren Quadrat sind.

Inhaltsverzeichnis

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ächstgrößere Primzahl, die 3. Anschließend werden deren Vielfache 9, 12, 15,… durchgestrichen, usw.

Das Sieb funktioniert auch (nur etwas langsamer), wenn immer alle Vielfachen (und nicht erst die ab der Quadratzahl) markiert werden. In dieser Form ist es bereits für Lernende der 6. Klasse verständlich. In der Regel wird in dieser Altersstufe auch noch ein Stück über \sqrt{S} hinaus gearbeitet, bis sich die Erkenntnis aufdrängt, dass nun „nichts mehr passiert“ (außer dass die Primzahlen noch ausgegeben werden müssen).

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

for i = 2 to 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
    endif
end

Optimiertes Verfahren: Es werden nur die bisher nicht markierten Vielfachen einer Primzahl markiert

Das Verfahren lässt sich optimieren, wenn nur die ungeraden Zahlen darin abgespeichert werden. 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


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Sieb des Eratosthenes — Sieb des Eratosthenes, s. Primzahl …   Meyers Großes Konversations-Lexikon

  • Sieb des Eratosthenes — I Sieb des Eratọsthenes,   ein auf Eratosthenes von Kyrene zurückgehender Algorithmus zur Ermittlung aller Primzahlen, die kleiner oder gleich einer vorgegebenen Grenze n sind. Hierzu schreibt man die Zahlen 2 bis n auf und streicht nacheinander …   Universal-Lexikon

  • Sieb des Atkin — Das Sieb des Atkin ist ein schneller, moderner Algorithmus zur Bestimmung aller Primzahlen bis zu einer vorgegebenen Grenze. Es ist eine optimierte Version des antiken Sieb des Eratosthenes: Das Atkinsieb leistet einige Vorarbeit und streicht… …   Deutsch Wikipedia

  • Netz 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. Inhaltsverzeichnis 1… …   Deutsch Wikipedia

  • Eratosthenes — von Kyrene (griechisch Έρατοσθένης ὁ Κυρηναῖος; * zwischen 276 und 273 v. Chr. in Kyrene; † um 194 v. Chr. in Alexandria) war ein außergewöhnlich vielseitiger griechischer Gelehrter in der Blütezeit der hellenistischen… …   Deutsch Wikipedia

  • Eratosthenes (Begriffsklärung) — Eratosthenes ist der Name von Eratosthenes von Kyrene (* ca. 276 v. Chr.; † 194 v. Chr.), griechischer Mathematiker, Geograph, Geschichtsschreiber, Philologe und Dichter sowie Direktor der Bibliothek von Alexandria Eratosthenes (Oligarch),… …   Deutsch Wikipedia

  • Eratosthenes von Kyrene — Eratosthenes von Kyrene,   griechischer Gelehrter, * Kyrene (heute Schahhat, Libyen) um 284 (oder 274) v. Chr., ✝ Alexandria um 202 (oder um 194) v. Chr.; Schüler von Zenon und Kallimachos; wurde 246 v. Chr. nach Aufenthalt in Athen durch… …   Universal-Lexikon

  • Eratosthenes — Eratosthenes,   griech. Gelehrter, *Kyrene (heute Schahhat, Libyen) um 284 v. Chr., +Alexandria um 202 v. Chr.; erfand das Sieb des Eratosthenes, ein Verfahren zur Bestimmung von Primzahlen …   Universal-Lexikon

  • Eratosthenes von Kyrene — Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Dabei werden Artikel gelöscht, die nicht… …   Deutsch Wikipedia

  • Sieb von Atkin — Das Sieb von Atkin ist ein schneller, moderner Algorithmus zur Bestimmung aller Primzahlen bis zu einer vorgegebenen Grenze. Es ist eine optimierte Version des antiken Sieb des Eratosthenes: Das Atkinsieb leistet einige Vorarbeit und streicht… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”