oleg@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