Das Sieb des Eratosthenes ist ein Algorithmus, mit dem alle Primzahlen bis zu einer bestimmten Zahl errechnet werden können. Es ist benannt nach dem griechischen Mathematiker Eratosthenes.
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.
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)
Eine Implementierung in der Programmiersprache Haskell sieht folgendermaßen aus:
primes = sieve [2..]
sieve (x:xs) = x : sieve [y | y <- xs, (y `rem` x) /= 0]
Weblinks
