Friday, December 8, 2006

Haskell code to list prime numbers


-- Just calculate the infinite list of primes (lazily),
-- then trip the range to fit
primeGenerator [start,end] = takeWhile (<= end)
. dropWhile (< start)
$ primes

-- Pointed notation with list comprehensions
primes = (2 : [x | x <- [3,5..], isPrime x])

-- Efficient test presupposes the existence of primes
-- This works because to determine whether p is prime you only need
-- to know the primes strictly less than p (except for 2 of course!)
isPrime x = null divisors
where divisors = [y | y <- onlyUpToSqrtX primes, x `mod` y == 0]
onlyUpToSqrtX = fst . span (<= sqrtX)
sqrtX = floor (sqrt (fromIntegral x))

-- A point-free notation, as an alternative
primes' = (2 : filter isPrime [3,5..]) -- indivisible n > 1
where isPrime = all (/= 0) -- i.e. all are nonzero of:
. remOf -- remainders of odd ints
-- where remOf n is when you
remOf n = map (mod n) -- divide into n a list of
. flip take primes' -- primes, but only
. length -- as many as
. takeWhile (<= n) -- are less than n, that is
. map (^ 2) -- the square of each of the
$ primes' -- primes



NOTE: all (/= 0) was provided by Bulat Ziganshin as an improvement on my orignal and . map (/=0).