Euler Sieve

• http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Euler.27s_sieve
• http://haskell.org/haskellwiki/Prime_numbers#Euler.27s_Sieve

Euler's sieve progressively removes, from all the natural numbers above 1, all the multiples of primes as the primes are found by it, starting with 2.

Closely related to the SieveOfEratosthenes.

In HaskellLanguage,

 primes = euler [2..]
 euler (x:xs) = x : euler (xs `minus` map (*x) (x:xs))

(this code uses "minus" from DataListOrdered package, with obvious semantics; is due to Daniel Fischer, posted on haskell-cafe mailing list).