Checking Primality Stops at the Square Root

A number is prime only when no allowed candidate divides it exactly

A prime number is an integer greater than 1 with no exact divisor other than 1 and itself. For the input 29, checking primality is a search through possible candidate divisors. If one candidate divides 29 exactly, 29 is not prime. If every required candidate fails, no extra divisor exists in the required range, so 29 is prime.

The search must distinguish one successful test from many failed tests. A single exact divisor is enough to disprove primality. Failed tests prove nothing by themselves until you have tested every candidate that could still be a divisor.

Testing through the square root cannot miss a larger factor of 29

If 29 had two nontrivial factors, they would form a pair whose product is 29. At least one member of any such pair must be no greater than the square root of 29. Otherwise both members would be greater than the square root, and their product would be greater than 29. Therefore, finding a factor larger than the square root would already require a smaller factor that should have been found first.

The square root of 29 lies between 5 and 6. That makes 2, 3, 4, and 5 the only candidate divisors that need testing. If all four fail, a candidate from 6 through 28 cannot be the first member of a new factor pair, because its matching factor would be below the square root and would already have been tested.

The loop must include the square-root boundary and stop at the first divisor

A prime check first rejects values below 2, then tests candidate divisors starting at 2. The loop must include the square-root boundary, because a factor can equal that boundary for some inputs. For 29, the safe condition tests 5 but stops before 6. As soon as an exact divisor appears, the function returns false instead of doing unnecessary tests.

if n < 2:
    return false

for i from 2 while i <= n / i:
    if n is divisible by i exactly:
        return false

return true

For 29, the loop visits the candidates in order. Candidate 2 does not divide 29 exactly, 3 does not divide it exactly, 4 does not divide it exactly, and 5 does not divide it exactly. The next candidate, 6, is outside the required range, so the search returns true after the four failed tests.

for (int i = 2; ______; i++)

Checking 29 takes constant space and only square-root-scale work

The check for 29 makes exactly four candidate tests: 2, 3, 4, and 5. In general, the loop makes at most about the square root of n candidate tests, so its time complexity is O(sqrt(n)). It uses only the input, the current candidate, and a few fixed values, so its extra space is O(1).

Testing every integer from 2 through 28 would make 27 tests for 29, even though candidates after 5 cannot reveal a new factor once the smaller side of every possible factor pair has failed. The square-root boundary removes that unnecessary work without changing the answer.