[Haskell-cafe] Genuine Eratosthenes sieve [Was: Optimization fun]
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:
-- 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..]
More information about the Haskell-Cafe