[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
```