= Solution
Use <trial division> on a shrinking residual. Once the trial divisor exceeds its <square root>, any residual larger than one is itself <prime>.
``
PROCEDURE divisors(n: INTEGER): INTEGER;
VAR residual, trial, exponent, answer: INTEGER;
BEGIN
residual := n; trial := 2; answer := 1;
WHILE trial * trial <= residual DO
exponent := 0;
WHILE residual MOD trial = 0 DO
residual := residual DIV trial;
exponent := exponent + 1
END;
answer := answer * (exponent + 1);
trial := trial + 1
END;
IF residual > 1 THEN answer := 2 * answer END;
RETURN answer
END divisors;
``
For the outer <loop invariant>, let $P$ be the set of <primes> below `trial` and $e_p$ their exponents in the original $n$. Then
$$
n=\mathrm{residual}\prod_{p\in P}p^{e_p},\qquad
\mathrm{answer}=\prod_{p\in P}(e_p+1),
$$
and `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$.
\b[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$.
Back to article page
