= 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`.
$$
\boxed{\mathrm{primeIter}(23):\quad2,3,5,7,11,13,17,19.}
$$
Bounds at most two give an empty <iterator>. This method tests candidates lazily and uses $O(\sqrt n)$ <trial divisions> for candidate $n$; no efficiency requirement in the question forces a <sieve of Eratosthenes> implementation.
Back to article page
