Crossing out the composites
The sieve of Eratosthenes finds all prime numbers up to a chosen limit n. Instead of testing each number for primality on its own, it works the other way around: it assumes everything is prime, then eliminates the numbers that cannot be.
How it works
- Create a boolean list for the integers from two up to n, all marked as prime.
- Start at the first prime, two. Mark every multiple of two above two as composite.
- Move to the next number still marked prime, three, and cross out its multiples.
- Continue with each surviving prime until you pass the square root of n.
Anything left marked prime at the end truly is prime.
Why stop at the square root
Any composite number has a factor no larger than its square root. So once you have sieved with every prime up to that point, every remaining composite has already been struck out by a smaller prime factor. You can also begin crossing out each prime at its square, since smaller multiples were already handled.
The sieve trades memory for speed and is far faster than trial dividing every number when you need many primes at once.
Key idea
The sieve discovers primes by elimination: cross out multiples of each small prime up to the square root of n, and whatever survives is prime.