# Eratosthenes

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.

### 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.

1. Draw a times table grid of numbers from 2 to 100 (leave the space for 1 empty).
2. Colour in all the numbers in the 2 times table in turn, apart from 2
3. Colour in all the numbers in the 3 times table in turn, apart from 3
4. Colour in all the numbers in the 4 times table in turn, apart from 4
5. Colour in all the numbers in the 5 times table in turn, apart from 5
6. Colour in all the numbers in the 6 times table in turn, apart from 6
7. … 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…

1. Draw a times table grid of numbers from 2 to 100 (leave the space for 1 empty).
2. Colour in all the numbers in the 2 times table in turn, apart from 2
3. Colour in all the numbers in the 3 times table in turn, apart from 3
4. Colour in all the numbers in the 5 times table in turn, apart from 5
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!).:

1. Draw a times table grid of numbers from 2 to 100 (leave the space for 1 empty).
2. 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
3. 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

### And on to programming …

So far we have used the same computational thinking skills as the Ancient greek Eratosthenes must have used to devise his Sieve algorithm to find prime numbers. Of course Eratosthenes didn’t have a computer to program. We do, so we can go a step further and now convert the algorithm for people to follow into a program to do the work for us, using more computational thinking, like decomposition, to do so…

Programming Challenge

Write a program to work out prime numbers using the sieve method.

What is the largest prime number can you compute with your program?

Need some help? Here is one way you might decompose the problem

1. Write a method to create a list of numbers to filter from 2 to a given number.
2. Write a method that given a list removes all those numbers in a given times table.
3. Write a method that applies the above over and over for each times table
4. Write your final method to create a list to filter using the first method and then sieving it using the third.
5. Call your final method, giving the number you want to filter up to, printing the result.

Write the methods one at a time and make sure they really do work before moving on to the next.

More help?

• If you are still learning to program and find that difficult to do that from scratch, then start with our simple cs4fn Python program that does a basic sieve.
• It creates a list of numbers to sieve. It then takes each number (2,3,4,5…) in turn and sieves out all numbers in its times table (apart from the first) by removing each in turn from the list.
• Load the program in to Python’s Development environment, IDLE. Run it and see what it does. Then see if you can work out how it works given the above description. You can do this by testing small parts of it at a time. Predict what you think they will do and then check if you are right. If you are wrong try to work out why.
• Here are some test commands to try to start. Type (or cut and paste them) one at a time. Look at the results carefully to help understand what they do.
• print (createlistupto(30))
• print(seiveOneTimesTable(createlistupto(30),2, 30))
• print(seiveOneTimesTable(createlistupto(30),3, 30))
• startlist = createlistupto(30)
• print(seiveOneTimesTable(startlist,2, 30))
• print(seiveOneTimesTable(startlist,3, 30))
• Edit the program to add some code so that it prints a message if after filtering for a times table no change was made.
• Edit the program to implement Eratosthenes more efficient algorithm so it doesn’t filter times tables that will make no difference. Do it a step at a time. Start with a version that cuts short the sieve when it gets to the square root of the biggest number being checked
• Next edit the program to implement Eratosthenes’ fully efficient version by only filtering out times tables of the prime numbers already found.

Make sure you test each version thoroughly.

More on Ancient Greek Algorithms

More on Computing Through History

This work was supported by the Institute of Coding, which is supported by the Office for Students (OfS).