> It's tricky to explain This reasoning is fairly simple: Suppose we have a composite number K that is less than P^2. Then K = A * B, for some A and B not eq

> It's tricky to explain This reasoning is fairly simple: Suppose we have a composite number K that is less than P^2. Then K = A * B, for some A and B not equal to 1, (which is the definition of composite). Let us say that A is less than or equal to B. (If this is not the case, switch the labels.) Then A must be less than P: If A is greater than P, K = A * B > A * P > P^2. But we chose K such that K < P^2. If A is less than P, then K will have been marked during the cycle of Q, a prime divisor of A, which will occur before P. Therefore, we do not need to examine any numbers below P^2 -- they are either prime or have been marked.