[Haskell-cafe] A tale of Project Euler

[Yitzchak Gale]

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