[Haskell-cafe] Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve)

[ajb at spamcop.net]

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