Brent Yorgey wrote:
For more information you might want to read this paper, which includes a much better primes implementation: www.cs.hmc.edu/~oneill /papers/Sieve-JFP.pdf In fact, this very same topic was discussed on the list a while back, you can read it here: http://thread.gmane.org/gmane.comp.lang.haskell.cafe/19699/focus=19798
While not nearly as good as O'Neil's sieve, I think this is a good compromise between beauty and speed: primes = 2 : 3 : sieve (tail primes) [5,7..] where sieve (p:ps) x = let (h, _:t) = span (< p*p) x in h ++ sieve ps (filter ((/=0).(`mod` p)) t) Often in Project Euler problems you need both a factorization function and a list of primes. In that case, I like this: primeFactors = pf primes where pf ps@(p:ps') n | p * p > n = [n] | r == 0 = p : pf ps q | otherwise = pf ps' n where (q, r) = n `quotRem` p isPrime = null . tail . primeFactors primes = 2 : filter isPrime [3,5..] -Yitz