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

The factorization-based version should produce the later outputs faster in this cost model. For an input $m$, it performs at most $O(\sqrt{m})$ trial-factor tests and $O(\log m)$ successful divisions, because each successful division removes a factor at least two. The square test uses multiplication, so it does not introduce an extra division on every loop test.

Across all candidates through $n$, the number of costly division or remainder operations is therefore at mostcompared with $\Theta (n^2)$ remainder operations for the straightforward routine. Small cases can still be affected by constant overhead; the conclusion concerns the growing enumeration workload, not a promise that every single call is faster.