Unfaithful Sieve vs Naive Prime Algorithm - See "The Genuine Sieve of Eratosthenes" by Melissa E. O'Neill

Naive.hs

module Main where

primes = 2 : [x | x <- [3..], isprime x]
isprime x = all (\p -> x `mod` p > 0) (factorsToTry x)
  where
    factorsToTry x = takeWhile (\p -> p*p <= x) primes

main = do
  let ps = take 10000 primes
  putStrLn $ (show . length $ ps) ++ " primes."

Output.txt

$ ghc -O2 Unfaithful.hs
$ time ./Unfaithful
10000 primes.

real	0m3.360s
user	0m3.339s
sys	0m0.018s

$ ghc -O2 Naive.hs
$ time ./Naive
10000 primes.

real	0m0.058s
user	0m0.053s
sys	0m0.003s

Unfaithful.hs

module Main where

primes = sieve [2..] 
  where sieve (p:xs) = 
          p : sieve [x | x <- xs, x `mod` p /= 0]

main = do
  let ps = take 10000 primes
  putStrLn $ (show . length $ ps) ++ " primes."