[Haskell-cafe] Re: Code and Perf. Data for Prime Finders (was:
Genuine Eratosthenes sieve)
ajb at spamcop.net
ajb at spamcop.net
Sun Feb 25 22:23:44 EST 2007
G'day all.
This one is pretty elegant. A Pritchard sieve is actually an
Eratosthenes sieve with the loops reversed. Unfortunately, it's
a bit slower. Maybe someone else can speed it up a bit.
mergeRemove :: [Integer] -> [Integer] -> [Integer]
mergeRemove [] ys = []
mergeRemove xs [] = xs
mergeRemove xs'@(x:xs) ys'@(y:ys)
= case compare x y of
LT -> x : mergeRemove xs ys'
EQ -> mergeRemove xs ys
GT -> mergeRemove xs' ys
pritchardSieve :: Integer -> [Integer]
pritchardSieve n
| n <= 16 = takeWhile (<=n) [2,3,5,7,11,13]
| otherwise = removeComposites [2..n] (sieve [2..n`div`2])
where
removeComposites ps [] = ps
removeComposites ps (cs@(c:_):css)
= removeComposites' ps
where
removeComposites' [] = []
removeComposites' (p:ps)
| p < c = p : removeComposites' ps
| otherwise = removeComposites (mergeRemove ps cs) css
pjs = pritchardSieve sn
sn = isqrt n
sieve [] = []
sieve (f:fs)
= composites pjs : sieve fs
where
composites [] = []
composites (p:ps)
| pf > n || f `mod` p == 0 = [pf]
| otherwise = pf : composites ps
where
pf = p*f
Cheers,
Andrew Bromage
More information about the Haskell-Cafe
mailing list