TAOCP 4.5.4 Exercise 2
No.
Section 4.5.4: Factoring into Primes
Exercise 2. [15] If it is known that the input $N$ to Algorithm A is equal to 3 or more, could step A2 be eliminated?
Verified: yes
Solve time: 2m32s
Solution
No.
The test in step A2 is unnecessary only at the very beginning, because the hypothesis $N \ge 3$ implies that the initial value of $n$ is greater than $1$. However, step A2 is also reached after every execution of step A5, and at that point $n$ may have become $1$.
Consider the input $N=4$.
After step A1,
$$ n=4,\qquad d_0=2. $$
Step A3 yields
$$ q=\lfloor 4/2\rfloor =2,\qquad r=0. $$
Step A5 outputs the factor $2$ and sets
$$ n\leftarrow q=2. $$
Returning to step A3 again,
$$ q=\lfloor 2/2\rfloor =1,\qquad r=0. $$
A second execution of step A5 outputs another factor $2$ and sets
$$ n\leftarrow 1. $$
If step A2 has been removed, the algorithm proceeds to step A3 with $n=1$. Then
$$ q=\lfloor 1/2\rfloor =0,\qquad r=1. $$
Step A4 transfers control to A6, and since $q>d_0$ is false, step A7 is executed. The algorithm incorrectly outputs
$$ p_t=1 $$
as an additional "prime factor."
Therefore step A2 is essential for detecting the case $n=1$ after all prime factors have been removed. The algorithm is not correct if A2 is simply eliminated, even when $N\ge3$.
$$ \boxed{\text{Step A2 cannot be eliminated.}} $$
This completes the proof.
∎