Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming / 2 / e / Solution

Use trial division on a shrinking residual. Once the trial divisor exceeds its square root, any residual larger than one is itself prime.For the outer loop invariant, let $P$ be the set of primes below trial and $e_p$ their exponents in the original $n$. Thenand residual has no prime factor below trial. If trial divides the residual it must therefore be prime: a composite trial value would have a smaller prime factor, contradicting this clause. If it does not divide, the zero exponent contributes the factor $1$.

For the inner loop invariant, let $r_0$ be the residual on entry. Then $r_0={\mathrm{trial}}^{\mathrm{exponent}}\mathrm{residual}$. Each exact division reduces the positive residual by at least a factor of two, so this loop terminates. At exit the exponent is the full multiplicity of trial; multiplying by exponent+1 preserves the outer loop invariant. The outer loop terminates because trial increases and residual never increases. When it exits, a composite residual would have a prime factor at most its square root, yet every smaller trial factor has already been excluded. Hence the residual is $1$ or a single remaining prime of exponent $1$.

The procedure computes $\tau (n)$ in $O(\sqrt{n})$ unit-cost time and $O(1)$ auxiliary space, with the separate successful divisions bounded by $\lfloor {\log }_{2}n\rfloor$. No array or table of primes is needed, and $n=1$ correctly returns $1$.