Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenSonntag, 15. September 2019 

Sieb des Eratosthenes


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Das Sieb des Eratosthenes ist ein Algorithmus mit dem alle Primzahlen bis zu einer bestimmten Zahl errechnet können. Es ist benannt nach dem griechischen Eratosthenes . Hinter diesem Algorithmus steckt das Prinzip alle natürlichen Zahlen größer eins zu den zu zählen; im Verlauf des Algorithmus werden irrtümlich angenommenen (Nicht-)Primzahlen dann heraus gesiebt. Der funktioniert nur dann wenn man ein begrenztes benutzt.

Der Algorithmus wird wie folgt ausgeführt:

  • Man streiche aus einer mit der 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 die nächsthöhere nicht durchgestrichene Zahl und streiche ihre Vielfachen.

Demonstrations-Animation:

Primzahl (die gesiebt wurde)
Nichtprimzahl
Primzahl (die durch Ausschluss übrig geblieben ist)

Beispiel:

 (2 3 4 5 6 7 9 10 11 12 ...) (2 3 5 / 7 / 9 / 11 ...) (streiche Vielfache von 2 aus) (2 / 5 / 7 / / / / ...) (streiche Vielfache von 3 aus) 3 / 5 / 7 / / 11 / ...) (streiche Vielfache von 5  

Eine Implementierung in der Programmiersprache Haskell sieht folgendermaßen aus:

 primes = sieve [2..] sieve (x:xs) x : sieve [y | y <- (y `rem` x) /= 0]  

Weblinks



Bücher zum Thema Sieb des Eratosthenes

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Sieb_des_Eratosthenes.html">Sieb des Eratosthenes </a>