Skip to content

Instantly share code, notes, and snippets.

@jnape
Last active October 14, 2015 00:08
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jnape/4277824 to your computer and use it in GitHub Desktop.
Save jnape/4277824 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes as infinite list of primes in Haskell
module Primes where
main :: IO ()
main = print $ take 1000 primes
(√) :: Int -> Int
(√) = floor . sqrt . fromIntegral
primes :: [Int]
primes = 2 : sieve [3, 5..]
where sieve (x:xs)
| isPrime x = x:sieve xs
| otherwise = sieve xs
none :: (a -> Bool) -> [a] -> Bool
none f = not . any f
isPrime :: Int -> Bool
isPrime x = none (\p -> rem x p == 0) $ possibleFactorsOf x
where possibleFactorsOf x = takeWhile (\p -> (√)x >= p) primes
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment