Why the sieve can stop at the square root
To find primes up to a chosen limit, the Sieve of Eratosthenes starts with the whole-number candidates and crosses out multiples of each prime in turn. The key question is when it has crossed out enough: why not keep checking divisors all the way to the limit?
The answer comes from how factors pair up. If a number is composite—meaning it can be made by multiplying two whole numbers greater than 1—its factors can be arranged as a pair. For example, 35 has factors 5 and 7. In any such pair, at least one factor must be no greater than the square root of the number. Otherwise, multiplying two factors both larger than the square root would produce a number larger than the number itself.
Smaller factors catch every composite
Suppose the sieve is looking for primes up to 100. Any composite in that range must have a factor no greater than 10, because √100 is 10. So once the sieve has processed the primes up to 10, every composite has already been crossed out by a smaller prime factor. A number still standing cannot have a hidden factor above 10 without also having a matching factor below 10.
This is why the sieve does not need to test every possible divisor for every candidate. It builds a shared “net”: when it reaches a prime such as 3, it removes all multiples of 3 at once, then moves on to the next remaining prime. By the time it passes the square-root threshold, all the composite numbers have been caught.
The stopping point is a consequence of factor pairs, not a shortcut that risks missing large factors. A composite may have a large factor, but that factor is always accompanied by a smaller one the sieve has already checked.
