1
\$\begingroup\$

I've implemented the Sieve of Eratosthenes algorithm in Haskell. Please take a look. Any suggestions are greatly appreciated :)

import Data.List

-- a list identical with {seq} but for multiples of {p} which are replaced by {-1}
sieve_once :: [Integer] -> Integer -> [Integer]
sieve_once seq p = map (\x -> if x `mod` p == 0 then -1 else x) seq

-- a list of all prime numbers
sieve :: [Integer]
sieve = unfoldr (\acc -> let p:rest = dropWhile (\x -> x == -1) acc in Just(p, sieve_once rest p)) [2..]

-- a list of all prime numbers not greater than {n}
sieve_until :: Integer -> [Integer]
sieve_until n = takeWhile (\x -> x <= n) sieve
\$\endgroup\$
3
\$\begingroup\$

I'd suggest to filter out unneeded elements, instead of replacing them by -1. Keeping and processing all the -1 is unnecessary:

sieve_once :: [Integer] -> Integer -> [Integer]
sieve_once seq p = filter (\x -> x `mod` p /= 0) seq

-- a list of all prime numbers
sieve :: [Integer]
sieve = unfoldr (\(p:rest) -> Just (p, sieve_once rest p)) [2..]
|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.