In part 1 we 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.
  • Here is our version
• 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
  • Here is our version
• Next edit the program to implement Eratosthenes’ fully efficient version by only filtering out times tables of the prime numbers already found.
  • Here is our version

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