An infinite list of primes, written in Haskell.

primes.hs

import Control.Applicative ((<|>))
import Data.Maybe (fromJust)


-- The primary task: Compute primes

-- Infinite list of primes
primes = iterate nextPrime 2 where
  nextPrime y = head [x | x <- [succ y..], hasNoFactors x]
  hasNoFactors x = fromJust $ foldr (<|>) Nothing $ map check primes where
    check y
      | y*y > x        = Just True
      | x `mod` y == 0 = Just False
      | otherwise      = Nothing


-- An application: Prime factorization

-- Infinite list of prime factorizations of x >= 2
allPrimeFactors = [(x,getFactors primes x) | x <- [2..]] where
  getFactors (y:ys) x
    | y*y > x        = [x]
    | x `mod` y == 0 = y : (getFactors (y:ys) $ x `quot` y)
    | otherwise      = getFactors ys x
  getFactors _ _ = []


-- Implementation of factorization using mutual recursion

primes2 = map fst $ filter ((== 1) . length . snd) allPrimeFactors2

allPrimeFactors2 = (2,[2]):[(x,getFactors primes2 x) | x <- [3..]] where
  getFactors (y:ys) x
    | y*y > x        = [x]
    | x `mod` y == 0 = y : (getFactors (y:ys) $ x `quot` y)
    | otherwise      = getFactors ys x
  getFactors _ _ = []


-- Print the prime factorizations of 2-1000000
main = mapM_ format (take (1000000-1) allPrimeFactors2) where
  format (n,fs) = putStrLn $ show n ++ " -> " ++ show fs