-- 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..]