Saturday, January 10, 2015

Sieve of Eratosthenes implementaion in haskell

-- Sieve of Eratosthenes implementaion in haskell
sieve :: [Integer] -> [Integer]
-- If it starts with zero, simply filter out
sieve (0:xs) = sieve xs
-- If it's not marked as 0, return it, and sieve the rest.
-- The rest is the result of marking multiple of n
-- The marking process is nested, for example:
-- 3 : sieve (mark (mark [4..] 2 2) 3)
sieve (n:xs) = n : sieve (mark xs 1 n) where
mark :: [Integer] -> Integer -> Integer -> [Integer]
-- This is just counting, staring from 1, 2, 3..., once it reaches n, it's rest to 1.
-- For every n numbers, there is one marked with 0, to be sieved out.
mark (y:ys) k m
| k == m = 0 : (mark ys 1 m)
| otherwise = y : (mark ys (k+1) m)

primes :: [Integer]
primes = sieve [2..]

0 comments: