imported>Horst Gräbner: Änderungen von ~2025-69413-1 (Diskussion) auf die letzte Version von Aka zurückgesetzt

2025-09-23T07:42:21Z

Änderungen von ~2025-69413-1 (Diskussion) auf die letzte Version von Aka zurückgesetzt

Neue Seite

Das '''Sieb des Eratosthenes''' ist ein [[Algorithmus]] zur Bestimmung einer Liste oder Tabelle aller [[Primzahl]]en kleiner oder gleich einer vorgegebenen Zahl. Es ist nach dem griechischen [[Mathematiker]] [[Eratosthenes]] 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.

Es ist das einfachste Beispiel von in der [[Analytische Zahlentheorie|analytischen Zahlentheorie]] verwendeten ausgefeilten Methoden der [[Siebtheorie]] (zum Beispiel von [[Adrien-Marie Legendre]], [[Viggo Brun]], [[Atle Selberg]], [[Alfred Renyi]], [[Pál Turán]], [[Juri Linnik]], [[Klaus Friedrich Roth]], [[Enrico Bombieri]], [[Askold Winogradow]], [[John Barkley Rosser]], [[Hugh Montgomery (Mathematiker)|Hugh Montgomery]], [[John Friedlander]], [[Henryk Iwaniec]], [[Roger Heath-Brown]]).<ref>George Greaves,''Sieves in Number Theory'', Springer 2001</ref><ref>[[Heini Halberstam]], [[Hans-Egon Richert]]: ''Sieve Methods'', London Mathematical Society Monographs 4, Academic Press 1974</ref> Der erste Schritt war die Verbesserung bzw. Umformulierung von Eratosthenes’ Sieb durch Legendre mit Hilfe der [[Möbiusfunktion]] mit zugehöriger Legendre-Identität und der Anfang moderner Siebmethoden war dessen Verbesserung durch Brun 1915.

== Funktionsweise ==
[[Datei:Animation Sieb des Eratosthenes Überarbeitet.gif|mini|300px|Basisverfahren: Es werden alle Vielfachen einer Primzahl markiert.]]
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 [[Vielfaches|Vielfachen]] dieser Primzahl als [[Zusammengesetzte Zahl|zusammengesetzt]] markiert. Man bestimmt die nächstgrößere unmarkierte 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 [[Quadratwurzel|Wurzel]] der Zahl sein muss, ist es ausreichend, nur die Vielfachen jener Primzahlen zu streichen, die kleiner oder gleich der Wurzel der Schranke S sind.

Ebenso genügt es beim Streichen der Vielfachen, mit dem [[Quadratzahl|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 11<sup>2</sup> = 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]]:

<syntaxhighlight lang="pascal">
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 Quadratwurzel von j <= n sein.
for i = 2 to sqrt(N) do
if not gestrichen[i] then
// i ist prim, gib i aus...
print i;
print ", ";
// ...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
</syntaxhighlight>

[[Datei:Animation schnell - Sieb des Eratosthenes.gif|mini|445px|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. 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 effizientere Verfahren als das Sieb des Eratosthenes (z. B. das [[Sieb von Atkin]]).

== Literatur ==
* [[Hans Magnus Enzensberger]]: ''Der Zahlenteufel. Ein Kopfkissenbuch für alle, die Angst vor der Mathematik haben.'' Hanser, München u. a. 1997, ISBN 3-446-18900-9.
* [[Kristin Dahl]], [[Sven Nordqvist]]: ''Zahlen, Spiralen und magische Quadrate. Mathe für jeden.'' Oetinger, Hamburg 2007, ISBN 978-3-7891-7602-9.

== Weblinks ==
{{Wikibooks|Primzahlen: Programmbeispiele|Quellcode des Algorithmus in verschiedenen Programmiersprachen}}
* [http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo25.php Ausführliche Erläuterung mit Animation] (Java-Applet)
* [http://www.hbmeyer.de/eratosib.htm Interaktive Animation] (erfordert JavaScript)
* [http://www.primzahlen.de/primzahltests/sieb_des_eratosthenes.htm Sieb des Eratosthenes – mit der Streichliste]
* {{TIBAV |19867 |Linktext=Sieb des Eratosthenes |Herausgeber=PHHD |Jahr=2012 |DOI=10.5446/19867}}
* [http://devalco.de/#106 Primzahlsiebkonstruktionen über quadratische, irreduzible Polynome]
== Einzelnachweise ==
<references />

[[Kategorie:Zahlentheoretischer Algorithmus]]
[[Kategorie:Primzahl]]

Sieb des Eratosthenes - Versionsgeschichte

imported>Horst Gräbner: Änderungen von ~2025-69413-1 (Diskussion) auf die letzte Version von Aka zurückgesetzt