Why does trial division only need to test divisors up to the square root of n?

## The claim To decide whether an integer `n > 1` is prime, it is enough to try candidate divisors `2, 3, 4, ... , floor(sqrt(n))`. If none of them divides `n`, then `n` is prime. Nothing above the square root needs to be tested. ## Why it is true Suppose `n` is composite. By definition it can be written as `n = a * b` with `1 < a <= b < n`. Now ask what happens if **both** factors were strictly greater than `sqrt(n)`: their product would be strictly greater than `sqrt(n) * sqrt(n) = n`, which contradicts `a * b = n`. So at least one of the two — the smaller one, `a` — satisfies `a <= sqrt(n)`. That is the whole argument. Divisors of `n` come in **pairs** `(d, n/d)`. Each pair straddles the square root: one member at or below it, the other at or above it. Scanning up to the square root visits the smaller member of every pair, so it cannot miss a factorization. Above the square root you are only re-discovering partners of divisors you already had a chance to see. A concrete pairing, for `n = 36`: `(1, 36), (2, 18), (3, 12), (4, 9), (6, 6)`. The scan `2..6` meets `2, 3, 4, 6` and stops. The partners `18, 12, 9` were never needed. ## Why "up to n/2" is the classic wrong answer `n/2` is not *incorrect* — no divisor of `n` other than `n` itself exceeds `n/2`, so the loop is valid. It is simply enormously wasteful. For a validator checking whether an order quantity near 1,000,000,000,000 can be split into equal groups, the square-root loop runs about 10^6 iterations; the `n/2` loop runs about 5 * 10^11. Same answer, five orders of magnitude apart. Interviewers ask this precisely because the two loops look equally reasonable to someone who has not thought about the pairing. ## The boundary, and the two bugs that live there 1. **Inclusive or exclusive.** A loop written `while i * i < n` never tests `i = 7` for `n = 49` and reports 49 as prime. Perfect squares are the only inputs where the smaller and larger partner coincide, so the bound must be `<=`. 2. **Computing the bound.** `i * i <= n` is the obvious form, but `i * i` can overflow a fixed-width integer when `n` sits near the top of the representable range, and an overflowed product can silently satisfy the comparison and end the loop early. Rewriting the same test as `i <= n / i` uses integer division, which never wraps, and is exact for this purpose. Taking a floating-point square root once and comparing against it is a third option, but floating-point rounding at the boundary means you must widen the limit by one and re-check — most people get that wrong, so the division form is the safer habit. 3. **Edge cases below the loop.** Values `n < 2` are not prime (1 has no second factor; 0 and negatives are outside the definition), and 2 is prime while every other even number is not. Handle those before the loop rather than hoping it does the right thing. ## The cost, and when the bound stops being enough Trial division to the square root costs O(sqrt(n)) divisions for one number. That is excellent for a **single** query — even for a value near 10^18 it is roughly 10^9 operations in the worst case, and far fewer in practice because most composites reveal a small factor immediately. A cheap refinement tests 2 and 3, then only candidates of the form `6k - 1` and `6k + 1`, since every other candidate is divisible by 2 or 3; that cuts the loop to about a third of its length without changing the O(sqrt(n)) class. Where the bound stops paying is **bulk** work. Testing every value in a range from 2 to `n` by trial division costs roughly `n * sqrt(n)` total, which collapses long before `n` reaches ten million. That is the moment to precompute the whole range once with a sieve instead of interrogating each number independently — the classic "one number versus a range" fork in this area. ## The mental model to carry The square-root bound is not an approximation, a heuristic, or a probabilistic shortcut that occasionally misses a factor. It is an exact consequence of divisors coming in pairs. Say the pairing argument out loud in an interview and the bound follows in one sentence; recite the bound without the argument and the next question — "are you sure that never misses?" — has nowhere to go.