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

The second procedure should reach large outputs faster, because the first makes exactly $n$ expensive MOD operations when processing argument $n$, whereas the second tries only up to the square root of a shrinking residual, with at most $\lfloor {\log }_{2}n\rfloor$ successful DIV operations. Each successful division also requires a successful MOD test; each outer iteration adds one final unsuccessful MOD test. Thus its expensive-operation count is $O(\sqrt{n}+\log n)$ per argument, and at most $O(n^{3/2})$ cumulatively through argument $n$, compared with $\Theta (n^2)$ for direct counting.

The speedup is not an assertion that every single call uses fewer divisions: for $n=4$, the second code makes three MOD tests and two DIV operations, while the first makes four MOD tests. Small constant costs can go either way. The many small prime factors in highly composite numbers also shrink the residual early, which often helps further; the cumulative comparison includes every preceding argument, not only the printed records.