= Solution
For the requested `Int`-typed operation, remove the first element as well as its later multiples:
``
sieve :: [Int] -> [Int]
sieve [] = []
sieve (p:xs) = [x | x <- xs, x `rem` p /= 0]
``
On its intended input, `p` is positive, so the <remainder> is defined. An arbitrary list headed by zero lies outside this convention.
To enumerate literally all <prime numbers>, use unbounded `Integer` arithmetic:
``
primes :: [Integer]
primes = go [2..]
where
go :: [Integer] -> [Integer]
go [] = []
go (p:xs) =
p : go [x | x <- xs, x `rem` p /= 0]
``
At each stage, the smallest remaining number has no smaller <prime divisor> and is therefore prime. Removing its larger multiples preserves every later prime and removes any <composite number> once its least <prime divisor> is processed. <Lazy evaluation> makes each requested finite prefix available. This implements the given repeated-filtering form of the <sieve of Eratosthenes>. A bounded `Int` stream can only cover representable values; `Integer` supplies the all-primes interpretation.
Back to article page
