Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 1 / c / Solution

By the time the candidate $n$ is emitted, every positive integer $m\le n$ has been examined. The straightforward divisor routine makes exactly $m$ remainder tests on $m$. Consequently the total number isand the time is $\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.