Definition
An ancient Greek math algorithm that finds prime numbers (natural numbers greater than 1 that divide evenly only by 1 and themselves) quickly and accurately. Just as you shake a sieve so the sand falls through and the pebbles stay behind, you start with the smallest prime and cross out its multiples one after another, until only the primes are left.
Why not just divide every number one by one?
Picture yourself gathering fine sand at the beach to build a sandcastle. Picking out pebbles by hand, one at a time, takes forever and a lot of effort. But if you pour the sand into a sieve full of holes and shake it, the big, rough stones get caught all at once.
Finding prime numbers works the same way. To check whether a number is prime, you could divide it by every number starting from 2. But the bigger the number gets, the more time that takes. Even just 1 to 100 means repeating a huge number of divisions.
Eratosthenes flipped this tedious process upside down. Instead of testing numbers one by one, he built a sieve that wipes out the multiples of primes all at once. You set 1 aside first, because it isn't prime. Then you find the smallest prime, 2, and start by sweeping away all the multiples of 2, like shaking them through the sieve.
Shake the sieve and knock out the multiples one by one
The first survivor is 2. Mark it as prime and circle it. Then cross out every multiple of 2 except 2 itself: 4, 6, 8, 10, and all the other even numbers. A huge heap of pebbles is gone from the sieve in a single pass.
Next, take the next number that hasn't been crossed out, 3, and mark it as prime. Then cross out the multiples of 3 except 3 itself: 6, 9, 12, 15, and so on. Some, like 6 and 12, were already crossed out as multiples of 2. But others, like 9 and 15, are new composite numbers getting caught.
The number 4 is already gone, so skip it. The next survivor is 5. Mark it as prime and cross out its multiples. If you patiently keep repeating this step of crossing out the multiples of each small survivor, all the composite numbers drop out, and in the end only the pure primes are left in the sieve, shining like jewels.
To be more precise: you don't have to go all the way
To be more precise, you don't need to cross out multiples for every number all the way to the end of your range. It's enough to check only up to the square root of the largest number you want to look at.
For example, if you want the primes among the natural numbers up to 100, you only need to cross out multiples up to 10, the square root of 100. The multiples of primes bigger than 10, like 11 or 13, have already been crossed out earlier, when you removed the multiples of 2, 3, 5, and 7. Take the multiples of 11 that are 100 or less: 22, 33, 55, and 77. Each of them is also a multiple of a smaller prime.
This clever shortcut cuts the amount of work dramatically. That's why, even in computer programming, when people need a list of primes across a huge range of tens of thousands or even hundreds of millions of numbers, they still rely on this sieving algorithm invented by an ancient Greek scholar thousands of years ago, along with its refined variations.
Common misconceptions
The Sieve of Eratosthenes is the best way to check whether one particular large number is prime.
To test just one large number, other primality tests are more efficient. The Sieve of Eratosthenes is considered an efficient method when you want the whole list of primes from 1 up to some limit, all at once.
Where you meet it
When you look for primes among the natural numbers from 1 to 100, crossing out only the multiples of 2, 3, 5, and 7 leaves 25 primes.
In computer programming, it's used when you need to generate lots of primes in a given range quickly.
In one sentence
An efficient algorithm that finds primes without dividing numbers one by one: it crosses out the multiples of each prime in turn until only the primes remain.