[Haskell-cafe] A tale of Project Euler
Yitzchak Gale
gale at sefer.org
Tue Nov 27 16:08:54 EST 2007
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
More information about the Haskell-Cafe
mailing list