# [Haskell-cafe] Genuine Eratosthenes sieve [Was: Optimization fun]

Yitzchak Gale gale at sefer.org
Mon Feb 12 05:03:34 EST 2007

oleg at pobox.com wrote:
> Still, in the interest of purity, here it is, in
> Haskell.  As the original Eratosthenes sieve,
> this algorithm uses only successor and
> predecessor operations.

I don't think the Greeks had too much trouble with
addition. If that is the case, then Rafael's
definition is still valid after a slight
modification, and still the clearest:

\begin{code}

-- Delete the elements of the first list from the second list,
-- where both lists are assumed sorted and without repetition.
deleteOrd :: Ord a => [a] -> [a] -> [a]
deleteOrd xs@(x:xs') ys@(y:ys')
| x > y       = y : deleteOrd xs  ys'
| x < y       =     deleteOrd xs' ys
| otherwise   =     deleteOrd xs' ys'
deleteOrd _ ys = ys

sieve (x:xs) = x : sieve (deleteOrd [x+x,x+x+x..] xs)
sieve _      = []

primes = sieve [2..]

\end{code}

Regards,
Yitz