LITMIR.BIZ

      FIGURE 1.20 Finally we are left with the primes from 1 to 100.

      The beautiful thing about this process it that it is very mechanical—it doesn’t require much thought to implement. For example, is 91 a prime? With this method you don’t have to think. 91 would have been struck out when you knocked out every 7th number on from 7 because 91=7×13.91 often catches people out because we tend not to learn our 7 times table up to 13.

      This systematic process is a good example of an algorithm, a method of solving a problem by applying a specified set of instructions—which is basically what a computer program is. This particular algorithm was discovered two millennia ago in one of the hotbeds of mathematical activity at the time: Alexandria, in present-day Egypt. Back then, Alexandria was one of the outposts of the great Greek empire and boasted one of the finest libraries in the world. It was during the third century BC that the librarian Eratosthenes came up with this early computer program for finding primes.

      It is called the sieve of Eratosthenes, because each time you knock out a group of non-primes it is as if you are using a sieve, setting the gaps between the wires of the sieve according to each new prime you move on to. First you use a sieve where the wires are 2 apart. Then 3 apart. Then 5 apart. And so on. The only trouble is that the method soon becomes rather inefficient if you try to use it to find bigger and bigger primes.

      As well as sieving for primes and looking after the hundreds of thousands of papyrus and vellum scrolls in the library, Eratosthenes also calculated the circumference of the Earth and the distance of the Earth to the Sun and the Moon. The Sun he calculated to be 804,000,000 stadia from the Earth—although his unit of measurement perhaps makes judging the accuracy a little difficult. What size stadium are we meant to use: Wembley, or something smaller, like Loftus Road?

      In addition to measuring the solar system, Eratosthenes charted the course of the Nile and gave the first correct explanation for why it kept flooding: heavy rains at the river’s distant sources in Ethiopia. He even wrote poetry. Despite all this activity, his friends gave him the nickname Beta—because he never really excelled at anything. It is said that he starved himself to death after going blind in old age.

      You can use your snakes and ladders board on the cover to put the Sieve of Eratosthenes into operation. Take a pile of pasta and place pieces on each of the numbers as you knock them out. The numbers left uncovered will be the primes.

      How long would it take to write a list of all the primes?

      Anyone who tried to write down a list of all the primes would be writing for ever, because there are infinitely many of these numbers. What makes us so confident that we’d never come to the last prime, that there will always be another one waiting out there for us to add to the list? It is one of the greatest achievements of the human brain that with just a finite sequence of logical steps we can capture infinity.

      The first person to prove that the primes go on for ever was a Greek mathematician living in Alexandria, called Euclid. He was a student of Plato’s, and he also lived during the third century BC, though it appears he was about 50 years older than the librarian Eratosthenes.

      To prove that there must be infinitely many primes, Euclid started by asking whether, on the contrary, it was possible that there were, in fact, a finite number of primes. This finite list of primes would have to have the property that every other number can be produced by multiplying together primes from this finite list. For example, suppose that you thought that the list of all the primes consisted of just the three numbers 2, 3 and 5. Could every number be built up by multiplying together different combinations of 2s, 3s and 5s? Euclid concocted a way to build a number that could never be captured by these three prime numbers. He began by multiplying together his list of primes to make 30. Then—and this was his act of genius—he added 1 to this number to make 31. None of the primes on his list, 2, 3 or 5, would divide into it exactly. You always got remainder 1.

      Euclid knew that all numbers are built by multiplying together primes, so what about 31? Since it can’t be divided by 2, 3 or 5, there had to be some other primes, not on his list, that created 31. In fact, 31 is a prime itself, so Euclid had created a ‘new’ prime. You might say that we could just add this new prime number to the list. But Euclid can then play the same trick again. However big the table of primes, Euclid can just multiply the list of primes together and add 1. Each time he can create a number which leaves remainder 1 on division by any of the primes on the list, so this new number has to be divisible by primes not on the list. In this way Euclid proved that no finite list could ever contain all the primes. Therefore there must be an infinite number of primes.

      Although Euclid could prove that the primes go on for ever, there was one problem with his proof—it didn’t tell you where the primes are. You might think that his method produces a way of generating new primes. After all, when we multiplied 2, 3 and 5 together and added 1, we got 31, a new prime. But it doesn’t always work. For example, consider the list of primes 2, 3, 5, 7, 11 and 13. Multiply them all together: 30,030. Now add 1 to this number: 30,031. This number is not divisible by any of the primes from 2 to 13, because you always get remainder 1. However, it isn’t a prime number since it is divisible by the two primes 59 and 509, and they weren’t on our list. In fact, mathematicians still don’t know whether the process of multiplying a finite list of primes together and adding 1 infinitely often gives you a new prime number.