= Solution
\b[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.
Back to article page
