Sieb des Eratosthenes
Das Sieb des Eratosthenes ist ein Algorithmus, mit dem alle Primzahlen bis zu einer bestimmten Zahl bestimmt werden können. Es ist benannt nach dem griechischen Mathematiker Eratosthenes. Hinter diesem Algorithmus steckt das Prinzip, anfangs alle natürlichen Zahlen größer eins zu den Primzahlen zu zählen; im Verlauf des Algorithmus werden die irrtümlich angenommenen (Nicht-)Primzahlen dann heraus gesiebt. Der Algorithmus funktioniert nur dann, wenn man ein begrenztes Zahlenfeld benutzt.
Der Algorithmus wird wie folgt ausgeführt:
- Man streiche aus einer mit der Zahl zwei beginnenden Liste natürlicher Zahlen bis zu einem gewünschten Maximalwert alle Vielfachen der ersten Zahl (also der Zwei).
- Wähle, solange es noch höhere Zahlen gibt, die nächsthöhere, nicht durchgestrichene Zahl und streiche alle ihre Vielfachen.
Demonstrations-Animation:
| Primzahl (die gesiebt wurde)
|
| Nichtprimzahl
|
| Primzahl (die durch Ausschluss übrig geblieben ist)
|
Beispiel:
(2,3,4,5,6,7,8,9,10,11,12,...)
(2,3,/,5,/,7,/,9, /,11, /,...) (streiche Vielfache von 2 aus)
(2,3,/,5,/,7,/,/, /,11, /,...) (streiche Vielfache von 3 aus)
(2,3,/,5,/,7,/,/, /,11, /,...) (streiche Vielfache von 5 aus)
Implementierungen
primes = sieve [2..]
sieve (x:xs) = x : sieve [y | y <- xs, (y `rem` x) /= 0]
- primzahlen.de/files/referent/kw/sieb.htm www.primzahlen.de/files/referent/kw/sieb.htm
Windows-Programm mit Quelltext in C++
madeasy.de/2/prgsieb.htm www.madeasy.de/2/prgsieb.htm Primzahlsieb in Visual Basic
faust.fr.bw.schule.de/mhb/eratosib.htm www.faust.fr.bw.schule.de/mhb/eratosib.htm Interaktive Animation (erfordert JavaScript)
anderegg-web.ch/phil/eratosthenes.htm Das Sieb des Eratosthenes erläutert
Der Ursprungsartikel stammt von der deutschsprachigen Wiki pedia (siehe oben: "Original Artikel & Autoren Liste").
Der Text steht unter der GNU Freie Dokumentation Lizenz. |