Question

Why does the Sieve of Eratosthenes work?

EXPERT ANSWER

If n is a composite number, then we can write n = ab, where {eq}1 leq a leq b leq n

{/eq}. We know that {eq}a leq sqrt{n}

{/eq}, since if {eq}a > sqrt{n}, ab > sqrt{n} sqrt{n} > n

{/eq}. a must have a prime divisor which is also a divisor of n, and thus must be {eq}leq sqrt{n}

{/eq}.

## We are so grateful