{-
Program : Prime.hs
Author : David Tran
Date : 2010-07-17
Below references show many ways to construct prime numbers:
* http://www.haskell.org/haskellwiki/Prime_numbers
* Melissa E. O’Neill, The Genuine Sieve of Eratosthenes
http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
http://lambda-the-ultimate.org/node/3127
The classic one-liner is very elegant:
primes = sieve [2..] where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p > 0]
However, it may be also the slowest…
The reason that I wrote my own version is because, after read yen3’s blog
(Chinese) http://yen3rc.blogspot.com/2010/03/haskell-practice-prime-2.html
I like to try the idea of list 6n+1 and 6n+5.
-}
module Prime (isPrime, primes) where
primes :: [Integer]
primes = 2:3:5: filter isPrime' ns
where ns = foldr (\n acc -> 6*n+1 : 6*n+5 : acc) [] [1..]
-- ns = concat $ zipWith (\x y -> [x,y]) [7, 13..] [11, 17..]
isPrime' :: Integer -> Bool
isPrime' n = check primes
where check (p:ps) | p < n' = if (n `mod` p == 0) then False else check ps
| otherwise = True
n' = truncate (sqrt $ fromIntegral n) + 1
isPrime :: Integer -> Bool
isPrime n | n < 2 = False
| otherwise = isPrime' n
{-
isPrime :: Integer -> Bool
isPrime n = n `elem` takeWhile (<=n) primes
-}