## Friday, December 8, 2006

### Haskell code to list prime numbers

`-- Just calculate the infinite list of primes (lazily),-- then trip the range to fitprimeGenerator [start,end] = takeWhile (<= end)                           . dropWhile (<  start)                           \$ primes-- Pointed notation with list comprehensionsprimes = (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 alternativeprimes' = (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).