Ancient Greek Computational Thinking – ERATOSTHENES | Teaching London Computing: A RESOURCE HUB from CAS LONDON & CS4FN

The Ancient Greeks loved algorithms, and devised lots of useful ones. One of the most famous is the Sieve of Eratosthenes. It is a way to find prime numbers, special numbers that are also known as the atoms of numbers. Prime numbers now form the basis of our most powerful encryption systems upon which digital money is based. Our electronic banking systems (and lots more) would collapse without prime numbers.

You can use the Sieve of Eratosthenes as a way to practice times tables, spot patterns and explore how to improve algorithms, whilst also uncovering these mysterious, magical numbers with no obvious pattern of their own. Here you can follow in the footsteps of Eratosthenes and develop your algorithmic thinking skills.

What are prime numbers?

What are prime numbers? They are just numbers that do not appear in any times table apart from their own… or as a mathematician might say more precisely they are “numbers greater than 1 that cannot be written as a product of two natural numbers that are both smaller than the number”.

Eratosthenes

The Sieve algorithm is named after Eratosthenes of Cyrene. He was a mathematician and all round scholar, though we remember him most for his prime number algorithm. He was also the chief librarian of the Library of Alexandria in Egypt, one of the most important libraries of the ancient world. As a result he was also the tutor of future Pharaohs. One of his other great achievements was to work out an algorithm for calculating the circumference of the Earth based on measurements of the length of a rod and of its shadow. (Yes he knew that the Earth was not flat but a sphere, unlike western Europeans who took centuries more to accept the fact!)

A simpler algorithm than Eratosthenes’

A simpler algorithm than Eratosthenes’ (that allows you to practice your time tables) is based on that fact that prime numbers are the ones not in any times table. It involves following these steps.

Draw a times table grid of numbers from 2 to 100 (leave the space for 1 empty).
Colour in all the numbers in the 2 times table in turn, apart from 2
Colour in all the numbers in the 3 times table in turn, apart from 3
Colour in all the numbers in the 4 times table in turn, apart from 4
Colour in all the numbers in the 5 times table in turn, apart from 5
Colour in all the numbers in the 6 times table in turn, apart from 6
… and so on …

The numbers left uncoloured are the prime numbers as they are not in any times table.

Perhaps you can see ways to do this faster? Do you need to go through every times table? If you can work out a faster way then you are doing the same computational thinking that Eratosthenes did over two thousand years ago to work out his fast Sieve algorithm. Try it before reading on.

Towards a better algorithm

The first thing you might have noticed is that there was really no point crossing out the 4 times table numbers. They were all already gone. Every number in the 4x table is also in the 2x table. The same is true of the 6 times table and so on. In fact we can ignore all the even number times tables once we have done the 2 times table. Our algorithm is immediately much faster…

Draw a times table grid of numbers from 2 to 100 (leave the space for 1 empty).
Colour in all the numbers in the 2 times table in turn, apart from 2
Colour in all the numbers in the 3 times table in turn, apart from 3
Colour in all the numbers in the 5 times table in turn, apart from 5
… and so on …

Now actually, exactly the same logic applies to the 3x table as well. Once you have crossed out everything in it, you have also crossed out all the 6 times and the 9 times tables too. There is no point in thinking about them either. In fact following this logic through, the times table of any number that is already crossed out, can be ignored as its whole times table will already be crossed out.

What is the next number whose times table you need to consider? It is just the next number that isn’t already crossed out (and in fact the next prime number). So after the 2x table is crossed out, the next number is 3. After that 5 is the next uncrossed out number and then 7, then 11 and so on.

Eratosthenes Sieve

Eratosthenes just thought through the above logic to give the final algorithm. Below is my version with colouring – Eratosthenes may not have liked colouring as much as I do, but why not de-stress yourself at the same time as playing with algorithms!).:

Draw a times table grid of numbers from 2 to 100 (leave the space for 1 empty).
Repeat until there are no numbers left uncoloured
1. Find the first number left in the grid that is not coloured in
2. Colour it in RED
3. Colour in all squares in that number’s times table BLUE
The numbers coloured RED are the prime numbers.

How far do you go?

There is one more easy improvement – about when to stop. You will find you can stop once you get to a prime that when squared is bigger than the last number in your table.

Think about our grid of numbers up to 100. This rule says that by the time we get to the 11 times table we will have removed everything there is to be removed, because squaring it takes you past the number 100.

Why? Everything 11 might remove for example has already gone: 22 because its in the 2 times table, 33 because its in the 3 times table ….99 because its in the 9 times table. It is only after we get to 11 times 11 and beyond we can possibly have new candidates to cross out, but they are beyond the extent of our grid of numbers to cross out. The same applies to all larger subsequent times tables we might use to cross numbers out,

Playing with Patterns

The reason the prime numbers are so useful in cryptography is to do with the lack of a simple pattern of which comes next. This means finding really big primes is difficult. Look at your grid – the primes jump about. You can compare this to the patterns of the different times table. Draw another 10×10 grid of numbers, this time with 1 to 100 in. Colour in the 2x table numbers – can you see a pattern? Take new grids and do the same for each of the times tables. For many, patterns will jump out at you (which you can use to help you remember them or work them out). Prime numbers you need to just remember or work out from scratch using the Sieve.

Activity Sheet