= Solution
Remove each <prime power> as soon as it is found, and stop trial division once the remaining value has no possible smaller factor:
``
def divisors(n: Int): Int = {
require(n >= 1)
var remaining = n
var factor = 2
var result = 1
while (factor.toLong * factor.toLong <= remaining.toLong) {
var exponent = 0
while (remaining % factor == 0) {
remaining /= factor
exponent += 1
}
result *= exponent + 1
factor += 1
}
if (remaining > 1) result *= 2
result
}
``
At an outer-loop boundary, write $n=q\,remaining$, where $q$ is the product of the <prime powers> already removed. The <invariant> states that `result` is $\tau(q)$, every prime <divisor> of $q$ is smaller than `factor`, and `remaining` has no prime <divisor> smaller than `factor`. Thus if `factor` divides `remaining`, it is prime; a composite factor would have a smaller prime <divisor>, contrary to the <invariant>.
During the inner loop, with $q$ fixed, $n=q\,factor^{exponent}\,remaining$. Each division removes one copy, so the positive remainder strictly decreases and supplies an inner-<loop variant>. On leaving the inner loop the complete power has been removed; multiplying the result by `exponent + 1` uses part (d) and reestablishes the outer <invariant> after advancing `factor`. The outer factor increases and can never exceed the original $n$ while its guard holds, proving termination.
At exit, a remainder greater than one must be prime: a composite remainder would have a prime factor no larger than its square root, which would still be smaller than `factor`. It therefore contributes one final factor of two. A remainder of one contributes nothing. \b[The <algorithm> returns $\tau(n)$ using constant <auxiliary space> and no <array>.] The widened multiplication in the loop guard prevents an `Int` overflow in the square test.
Back to article page
