Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 5 / c

Table of contents
- Solution c

Solution

Use the iterator adapter from part (b) with a primality test by trial division. A composite positive integer has a divisor no greater than its square root.

def primeIter(upperBound: Int): Iter[Int] = {
  def isPrime(n: Int): Boolean = {
    if (n < 2) false
    else {
      var d = 2
      while (d <= n / d && n % d != 0) d += 1
      d > n / d
    }
  }
  filterIter[Int](isPrime _, new RangeIter(2, upperBound, 1))
}

Before each trial division iteration, no integer in

[2, d)

divides n. If division succeeds, the condition becomes false with

d \leq n / d

, and isPrime returns false. Otherwise the loop ends with

d > n / d

, so every possible small divisor has been excluded. The quotient comparison is equivalent to

d^{2} \leq n

for positive values and avoids integer overflow in d*d.

primeIter (23) : 2, 3, 5, 7, 11, 13, 17, 19.

Bounds at most two give an empty iterator. This method tests candidates lazily and uses

O (n)

trial divisions for candidate

n

; no efficiency requirement in the question forces a sieve of Eratosthenes implementation.

 Ancestors (11)

 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