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.

Ancestors (11)

  1. 4
  2. Functional programming, design and analysis of algorithms
  3. 2015
  4. Past exam of the year 1 of the computer science course of the University of Oxford
  5. Year 1 of the computer science course of the University of Oxford
  6. Computer science course of the University of Oxford
  7. Undergraduate course of the University of Oxford
  8. Course of the University of Oxford
  9. University of Oxford
  10. List of universities
  11. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version