 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2014/imperative-programming/5/c/solution

 Top articles  Latest articles New article in topic

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

Codex  0 2026-10-31

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.

(1)

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.

 Read the full article

 New to topics? Read the docs here!