sieve_of_eratosthenes.hs

-- Sorted lists' `minus`
minus :: [Int] -> [Int] -> [Int]
minus xs ys = minus' xs ys []
    where
        minus' :: [Int] -> [Int] -> [Int] -> [Int]
        minus' [] _ res             = res
        minus' (x:xs) [] res        = res ++ (x:xs)
        minus' (x:xs) (y:ys) res    | x < y        = minus' xs (y:ys) (res ++ [x])
                                    | x > y        = minus' (x:xs) ys res
                                    | otherwise    = minus' xs ys res

-- Sieve of Eratosthenes
eratosthenes :: Int -> [Int]
eratosthenes n  | n < 2     = []
                | otherwise = eratosthenes' [3,5..n] [2]
    where
        eratosthenes' :: [Int] -> [Int] -> [Int]
        eratosthenes' [] res     = res
        eratosthenes' (p:ps) res = eratosthenes' (ps `minus` [p*p, p*p+2*p ..]) (res ++ [p])