The Sieve of Eratosthenes

Is 91 prime? It is odd, so 2 is not a factor. Its digits add up to 10, so 3 is not a factor either. It looks prime. But 91 = 7 × 13, so it is composite. Testing numbers one at a time is slow, and easy to get wrong. Is there a better way to find all the primes up to 100?

A man who measured the Earth

About 2,200 years ago a Greek scholar called Eratosthenes lived in Alexandria, in Egypt. He was born in Cyrene, in what is now Libya, around 276 BC, and ran the great library of Alexandria. He is famous for measuring the size of the Earth with shadows. He is also remembered for a way of finding primes. It is called the sieve of Eratosthenes. A sieve is a kitchen tool full of small holes: you pour flour through it, and the lumps stay behind. His sieve lets the composite numbers fall through, and the primes stay behind.

How the sieve works

Write the numbers from 1 to 100 in a square, ten in each row. Then:

1. Cross out 1. It is not a prime.
2. Circle 2, the first prime. Cross out all the other multiples of 2: 4, 6, 8, 10 and so on. They all have 2 as a factor, so none of them is prime.
3. The next number not crossed out is 3. Circle it, and cross out the multiples of 3: 6, 9, 12, ... (some are crossed out already).
4. 4 is crossed out. The next one left is 5: circle it, cross out its multiples.
5. Then 7: circle it, cross out 14, 21, 28, ... 91, 98.

Each number you cross out is a multiple of a smaller number, so it has a factor that is not 1 or itself. Each number that is never crossed out has no smaller factor except 1, so it is prime.

When can we stop?

The next prime is 11. Its multiples are 22, 33, 44 and so on up to 99. But each of those is 11 times a number smaller than 11 - 22 is 11 × 2, 33 is 11 × 3 - so it was already crossed out when we sieved with 2, 3, 5 or 7. The first multiple of 11 that is new is 11 × 11 = 121, which is past 100.

So after 7 the work is done. Every number still standing is a prime. Circle them all: there are 25 primes up to 100.

Look at the circled numbers. Except for 2 and 5, they all end in 1, 3, 7 or 9. They come in no simple pattern, and that is one of the great puzzles of mathematics.

Try it at home

1. Draw the numbers 1 to 50 in five rows of ten. Sieve them with 2, 3, 5 and 7. How many primes are left?
2. Why don't you need to sieve with 7 for the numbers up to 48?

Answers: 1. 15 primes (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47); 2. the first new multiple of 7 is 7 × 7 = 49.

Words to know

• sieve - a tool with holes that lets small things through and keeps the rest; in maths, a way of crossing out numbers to leave the ones you want
• sieve of Eratosthenes - finding the primes by crossing out the multiples of each prime in turn

Big idea

Cross out the multiples of 2, 3, 5 and 7, and the numbers left standing up to 100 are exactly the primes - 25 of them. You can stop once a prime times itself is past the end.