= Solution
By the time the candidate $n$ is emitted, every <positive integer> $m\leq n$ has been examined. The straightforward <divisor> routine makes exactly $m$ remainder tests on $m$. Consequently the total number is
$$
\sum_{m=1}^{n}m=\frac{n(n+1)}2,
$$
and the time is \b[$\Theta(n^2)$] when remainder tests and the other fixed-width operations have constant cost and printing is cheap. Emitting only record candidates does not avoid computing the <divisor> count of the intervening candidates.
Back to article page
