= Solution
\b[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 most
$$
O\!\left(\sum_{m=1}^{n}(\sqrt m+\log m)\right)=O(n^{3/2}+n\log n),
$$
compared 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.
Back to article page
