TAOCP 4.5.4 Exercise 21
The previous argument fails because it interprets $m(p)$ as the number of repeated divisions by $p$ after the algorithm has already reached the trial divisor $p$.
Section 4.5.4: Factoring into Primes
Exercise 21. [M29] (R. K. Guy.) Let $m(p)$ be the number of iterations required by Algorithm B to cast out the prime factor $p$. Is $m(p) = O(\sqrt{p} \log p)$ as $p \to \infty$?
Verified: yes
Solve time: 12m09s
Solution
The previous argument fails because it interprets $m(p)$ as the number of repeated divisions by $p$ after the algorithm has already reached the trial divisor $p$. That is not the quantity measured by Algorithm B.
In Algorithm B, an iteration is a pass through the main loop that advances the current trial divisor. Therefore, in order to cast out the prime factor $p$, the algorithm must first reach $p$ among its trial divisors. The dominant cost is the search for $p$, not the subsequent repeated divisions by $p$.
Let $m(p)$ denote the number of iterations required before the factor $p$ is cast out.
Algorithm B uses the wheel modulo $30$. After the special treatment of $2,3,5$, the successive trial divisors are precisely the integers relatively prime to $30$:
$$ 1,7,11,13,17,19,23,29,31,\ldots $$
Among every block of $30$ consecutive integers, exactly
$$ \varphi(30)=8 $$
survive. Hence the number $N(x)$ of admissible trial divisors not exceeding $x$ satisfies
$$ N(x)=\frac{8}{30}x+O(1). $$
Take as input $n=p$, where $p$ is prime. In this case no factor is found before the trial divisor reaches $p$, so the number of iterations required is exactly the index of $p$ in the wheel sequence, up to an additive constant. Therefore
$$ m(p)=N(p)+O(1) =\frac{8}{30}p+O(1). $$
Consequently
$$ m(p)=\Theta(p). $$
Now compare this with $\sqrt p,\log p$:
$$ \frac{m(p)}{\sqrt p,\log p} \sim \frac{8}{30}, \frac{\sqrt p}{\log p}. $$
Since
$$ \frac{\sqrt p}{\log p}\to\infty \qquad (p\to\infty), $$
it follows that
$$ \frac{m(p)}{\sqrt p,\log p}\to\infty . $$
Hence $m(p)$ is not bounded by a constant multiple of $\sqrt p\log p$.
Therefore
$$ \boxed{m(p)\neq O(\sqrt p,\log p)}. $$
In fact,
$$ \boxed{m(p)=\Theta(p)}. $$
This answers Guy's question in the negative. ∎