Sieve of Eratosthenes
Just like sifting gravel out of sand, it is math's clever strainer that filters out composite numbers to leave only pure primes behind.
Definition An ancient Greek algorithm designed to find prime numbers quickly and accurately. Much like shaking a sieve to separate fine sand from pebbles, this method systematically crosses out multiples of each prime starting from the smallest, leaving behind only the prime numbers.
Why Not Test Every Single Number by Division?
Imagine gathering fine sand to build a sandcastle on the beach. Picking out every tiny pebble one by one with your fingers takes forever. Instead, if you pour the sand into a mesh sieve and shake it, you can filter out all the chunky pebbles all at once.
Finding prime numbers works the same way. Trying to check whether a number is prime by dividing it by every single smaller number takes way too long as numbers grow large. Even testing numbers from 1 to 100 requires countless division steps.
Eratosthenes flipped this tedious process on its head. Instead of testing each number individually, he built a sieve that eliminates all multiples of primes at once. Since 1 is not a prime, we set it aside first. Then, starting with the smallest prime, 2, we begin filtering by crossing out all multiples of 2.
Shaking the Sieve: Eliminating Multiples Step by Step
The first surviving number, 2, is marked as a prime. Next, we cross out all multiples of 2 except 2 itselfโ4, 6, 8, 10, and so on. In a single sweep, an entire pile of even-number "gravel" drops out of the sieve.
Next, the smallest uncrossed number left is 3, which we confirm as prime. We then eliminate all remaining multiples of 3 (excluding 3 itself), like 6, 9, 12, and 15. Some, like 6 and 12, were already crossed out as multiples of 2, but new composite numbers like 9 and 15 get filtered out here.
Since 4 is already crossed out, we skip it and move to 5, mark it as prime, and cross out its multiples. By steadily repeating this process of crossing out multiples of surviving numbers, all composite numbers fall away, leaving only pure prime numbers resting like gems in the sieve.
A Clever Shortcut: You Don't Have to Check to the End
To be more precise, you never need to check multiples of every single number up to the upper limit. You only need to test numbers up to the square root of your target maximum to find every prime perfectly.
For example, if you want to find all primes up to 100, you only need to cross out multiples of primes up to the square root of 100, which is 10. Multiples of primes greater than 10 (like 11 or 13) were already eliminated in earlier steps by 2, 3, 5, or 7. For instance, any multiple of 11 under 100โsuch as 22, 33, 55, or 77โis already a multiple of one of those smaller primes.
This smart shortcut drastically slashes the work needed. That is why modern computer programming still relies on this ancient filtering algorithm invented thousands of years ago whenever it needs to generate massive lists of prime numbers.
๐ค Common misconceptions
The Sieve of Eratosthenes is the best method to check if a single large number is prime.
For testing just one specific number, other primality tests are much faster. The Sieve of Eratosthenes is most powerful when finding all prime numbers within a given range at once.
๐งบ Where you meet it
An efficient algorithm that finds prime numbers by crossing out multiples of primes in bulk rather than testing numbers one by one through division.