In the Sieve of Eratosthenes, why does crossing out multiples of p start at p squared?

## What the sieve does The Sieve of Eratosthenes computes primality for **every** number in `2..n` at once. It keeps one flag per candidate, initially "prime", walks upward, and whenever it finds a still-unmarked value `p`, marks every multiple of `p` in range as composite. What survives is exactly the set of primes. The naive inner loop starts at `2 * p`. The standard one starts at `p * p`. Both are correct; the interview question is *why the second one loses nothing*. ## The argument Take any multiple of `p` strictly below `p * p`. It can be written as `p * k` where `2 <= k < p`. Since `k >= 2`, it has at least one prime factor `q`, and `q <= k < p`. Because the outer loop walks upward and `q < p`, the prime `q` was already processed, and at that moment the loop over multiples of `q` marked every multiple of `q` in range — including `p * k`, which is one of them. So every multiple of `p` below `p * p` is *guaranteed* to be already marked. The first multiple of `p` that no smaller prime can have reached is `p * p` itself, whose only prime factor is `p`. Tracing it makes the pattern obvious. For `p = 5` with `n = 30`, the multiples `10, 15, 20` fell to 2, 3 and 2 respectively; the inner loop starting at 25 writes only `25` and `30`. (Note that `30` is written again — starting at `p * p` removes the redundancy *below* the square, not all of it. Composites keep getting marked once per distinct prime factor at or below their smallest square-reachable prime.) ## What it costs, and what it does not The total work of the sieve is the number of marks written: roughly the sum over primes `p <= n` of `n / p`. By a classical result the sum of `1/p` over primes up to `n` grows like `ln ln n`, so the sieve is **Θ(n log log n)** — near-linear, which is why sieving ten million values is milliseconds-to-tens-of-milliseconds of arithmetic. Starting at `p * p` removes, for each prime `p`, the marks at `2p, 3p, ..., (p-1)p` — about `p` writes. Summed over the primes up to the square root of `n`, that is a lower-order quantity compared with `n log log n`. So the honest answer to "does it change the complexity?" is **no**: it is a real, measurable constant-factor win, and the asymptotic class is unchanged. Claiming it takes the sieve from `O(n log n)` down to `O(n log log n)` is the confident-sounding wrong answer here; the `log log` factor comes from the harmonic-over-primes sum, not from the starting index. ## The companion optimisation: stopping the outer loop Once `p > sqrt(n)`, `p * p > n`, so the inner loop has no work in range at all. That means the outer loop can stop at the square root, and every flag still unmarked above it is prime by construction — the same divisor-pairing fact that bounds single-number trial division, applied to a whole range. Be careful to keep the *reading* of the flag array over the full `0..n` even though the *marking* loop stops early. ## Boundary details that decide whether your version is right - `0` and `1` must be marked non-prime explicitly; the marking loop never touches them. - The guard for "is there any work for `p`?" is best written `p <= n / p` rather than `p * p <= n`, because `p * p` can wrap a fixed-width integer when `n` is near the top of the range, and a wrapped product can compare as in-range and send the inner loop to a garbage index. - `p` itself must not be marked — the inner loop begins strictly at `p * p`, which is why the very first write for `p = 2` is `4`, not `2`. ## Pseudocode, and what to say while tracing it ``` for p in 2..n if is_prime[p] j = p * p while j <= n is_prime[j] = false j = j + p ``` The two sentences an interviewer wants: "the outer loop only enters the body for primes, because composites were already unmarked before we reached them", and "the inner loop starts at the square because everything below it carries a smaller prime factor that already did the job". Both are about the invariant — when the walk arrives at index `p`, all composites with a prime factor below `p` are already marked — and stating that invariant explicitly is what separates a memorised sieve from an understood one. ## Where the sieve is the wrong tool If you need primality for a handful of specific large values rather than a whole range, the sieve is the wrong shape: it pays memory proportional to the range ceiling to answer questions you did not ask. Per-number testing costs nothing but time proportional to the square root. The sieve wins exactly when the query count is large relative to the range.