# The Sieve of Eratosthenes

Mathematicians have always been fascinated by prime numbers – the raw material from which all numbers are made. A prime number is any number that can only be divided by two different numbers, itself and 1, without producing a remainder. (The number 1 isn’t considered a prime number, since it can only be divided by itself).

Every other number – the ‘non-primes’ – can be produced by multiplying together a combination of two or more prime numbers, and every such combination is unique. As a result, everything that can be counted is actually a combination of one or more prime numbers. Prime numbers are the foundation of the universe.

The problem for mathematicians is that prime numbers are a mystery. Many wonderful things – and many very complicated things – are known about prime numbers. But so far no-one has ever solved the problem of predicting exactly where prime numbers will occur amongst their non–prime colleagues.

Of course, the list of known prime numbers is staggeringly long. Even before the advent of computers, there were huge tables of prime numbers. But every one of the numbers on that list was originally discovered by someone (or some thing, nowadays) looking at the number and starting the laborious task of deciding whether is can be divided by something smaller, without leaving a remainder.

Today, all the prime numbers are known up to unimaginable values. The largest known has no less that 17,425,170 digits (at the time of writing). But for all the sophistication of modern methods, the only way the next larger one will be found is by looking at successively larger numbers and asking, ‘is there something smaller that will divide this’.

That said, mathematicians have discovered ways to reduce the amount of work necessary to get the answer to that question. One of the earliest is attributed to Eratosthenes, a mathematician (an all round genius) who lived in the third century BC. His insight, which may seem blindingly obvious now – as most insights of true genius do after the event – was to see that rather than looking for the prime numbers, it would be easier to list all the numbers and then take away all the ones that weren’t prime.

So he took a list of, say, the first 100 numbers, and successively removed all the multiples of two – 2, 4, 6, 8 etc. You didn’t even need to do any multiplication, you could just count along the list two at a time. When all the twos had gone, you did the same thing for the next prime number, 3. Then you did the same thing for 5, 7, 11 in turn. It turned out that once you had dealt with 11, there were no numbers left that were multiples of anything. All you had left were the prime numbers up to 100.

The ‘Sieve of Eratosthenes’ is often pictured as a square (often 11*11) with non-primes removed or coloured. Here we use a triangle, purely because is makes nicer patterns. Different colours are used successively to colour multiples of 2, then 3, then 5, then 7, then 11. The rule adopted, and it’s purely arbitrary, is that if a number is divisible by 2 and by, say, 7, such as 28, it gets the colour of the larger number. The numbers themselves are not shown because it’s the patterns (or the nearly-patterns) that are the interesting thing. The prime numbers are the blanks.

You can always try for yourself putting numbers into an orderly pattern and then marking the primes – spiralling out from 1, or following the outline of a star, or a leaf. One day, someone doing just that may look at the resulting pattern and say: ‘So that’s how prime numbers work!’ Their name would never be forgotten.