Sieve of Eratosthenes.

furui.hs

import System.Environment (getArgs)

data PFilter a = PFilter a (a -> Bool)

instance Show a => Show (PFilter a) where
  show (PFilter s _) = "PF " ++ show s

mfilter :: Integral a => a -> a -> Bool
mfilter p x = (x `mod` p) /= 0

type Furui = ([Integer], [PFilter Integer])

apply_filter :: Furui -> Furui
apply_filter (xs@(x:_), pfs@(PFilter s f:pfs'))
  | x >= s    = (filter f xs, pfs')
  | otherwise = (xs, pfs)

append_filter :: Furui -> Integer -> Furui
append_filter (xs, pfs) p = (xs, pfs ++ [PFilter (p*p) (mfilter p)])

initial_furui :: Furui
initial_furui = ([2..], [])

next_prime :: Furui -> (Integer, Furui)
next_prime (p:ps, fs) = (p, apply_filter $ append_filter (ps, fs) p)

primes :: [Integer]
primes = primes_rec initial_furui
  where primes_rec :: Furui -> [Integer]
        primes_rec f = let (p, f') = next_prime f
                       in p:primes_rec f'

strtoi :: String -> Maybe Integer
strtoi str = v $ reads str
  where v [] = Nothing
        v ((x,_):_) = Just x

main = do args <- getArgs
          case args of
            []  -> putStrLn "Missing argument."
            a:_ ->
              case strtoi a of
                Nothing -> putStrLn $ "Invalid argument: "++a
                Just n -> mapM_ (putStrLn.show) (takeWhile (<n) primes)