Das Sieb des Eratosthenes ist ein Algorithmus, mit dem alle Primzahlen bis zu einer bestimmten Zahl errechnet werden können.
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
- http://home.t-online.de/home/0926161717-0002/prgsieb.htm
- Programmbeispiel in Visual Basic