Last week, we used an ancient algorithm -- the Sieve of Eratosthenes --
to find all the prime numbers less than N. This week, we will use
graphics to illustrate the pattern of the primes. Along the way, we'll learn a lot about the graphical abilities of Python.
The Sieve algorithm can be illustrated graphically with pen and paper, using a number square like the one below:
On the Wikipedia page, you can find a colourful animation of the process of "crossing off" multiples of 2, 3, 5, etc.
Last week, we wrote a program to implement the Sieve algorithm with lists. This week we will write a graphical Python program to illustrate the process of crossing off numbers, by generating images like this one:
Here, each of the numbers from 0 up to (197)^2 corresponds to a "pixel" on screen: i.e. a tiny coloured square. The numbers increase as we read from left to right, and top to bottom, across the image (this is just a larger version of the number square). The white pixels are prime numbers (e.g. 5), and the blue pixels are composite numbers (e.g. 6 = 3 x 2).
To harness the graphical abilities of Python, we will use two packages:
Let's load an image from file, and display it on screen, using pygame.
Open a new Python file, and save it. Now download the image file, attached at the bottom of this page,
What does this code do? Let's go through it line-by-line. First, we import the
Try running this code -- does it work for you? If not, take a look at the error message. Can you work out what's wrong? Here are some possibilities: (1) pygame is not installed, (2) you are not using Python version 2.7 (i.e. IDLE, rather than IDLE3), (3) the image file could not be loaded, perhaps because it's not in the same directory as your Python file.
There is one problem with this program: once the window has appeared, we can't seem to close it down! To fix this problem, we need to add code which responds to events as they happen. In this case, to respond to the user's request to close the window. A minimal example is given below:
What does this code do? Well, it responds to "events" as they arise. What is an event? Whenever the user clicks a mouse button, or presses a key, or closes the window, a new event is created, and added to the "event queue". The code above repeatedly checks the event queue for new events (using
Programs with a "User Interface" are often event-driven. They wait for events, and respond accordingly. Let's explore this approach by writing a simple program which lets the user draw straight lines in a window. We will check the event queue for "mouse click" events.
Try replacing the "while not done" loop with the following code.
Do you see how it works? The program responds to a left mouse button click, by (a) reading the coordinates of the cursor's position on the screen, and adding to a list, (b) drawing a new line if there are two or more points in that list. It responds to a right button click by resetting the list of points.
A simple program
You may find the code above confusing, because it looks rather different to the examples from previous weeks. This is because we have encountered another new idea: object-orientated programming. But what are objects? Roughly speaking,
Now let's look at how we use the Surface object. The very next line is:
Here, we are calling a method (a function) defined in the Surface class: namely, blit. Blit copies one Surface onto another Surface. In this case, we are copying the "image" Surface (previously obtained with pygame.image.load) onto the display Surface.
We have seen how to load and display an image, and how to draw lines in a window. Along the way we've learnt a little bit about object-orientation. Our aim in this section is to learn how to modify the pixels individually (i.e. modify the tiny squares that make up the picture).
As we've seen, Pygame uses a particular "object" for representing images, called a Surface. Unfortunately, this object does not give us direct access to the pixels themselves. Fortunately, there is a closely-related module which gives us just what we need. Surfarray is a pygame module for accessing surface pixel data using array interfaces.
We can think of the screen as being made up of a table of pixels. Each value in the table corresponds to the color of a particular pixel. In pygame, this table is represented by a 2D array. We can modify the pixels individually, by modifying the values in the array.
What is an array? An array is data structure (type of memory layout) that stores a collection of individual values that are of the same data type. All of the items placed into an array are automatically stored in adjacent memory locations. This makes it efficient for a program to access and process the information stored in an array.
How is an array different to a list? A list is much more flexible: you can store different types of information in a list (e.g.
What is a 2D array? A 2D array is like a table of data. Whereas the elements in a 1-dimensional array are referenced with a single index, the elements in a 2-dimensional array are referenced with two indices, corresponding to the "row" and "column" position.
How do I define an array in Python? Arrays are not implemented in the core language, although you can use list-of-lists. Arrays are implemented by
Now we want to modify the pixels directly. Let's write some example code. The first part will create a new window - you've seen how to do this already:
I have chosen to make the screen a square of width 256. This is a special number for computers: 256 = 28. One byte of memory is 8 bits, each of which is either 1 or 0. So one byte of can represent one of 256 different numbers (i.e. 0,1,2, ... 255). Colours are specified by three RGB values: the amount of red, the amount of blue and the amount of green. Each number should be between 0 and 255.
Now we need some code to: (i) read the array of RGB values representing the pixels, (ii) modify that array, (iii) write the modified array of pixels back on to the screen. Let's try this:
Can you see what this code does? If not, try looking up each statement in turn. Here, the colour value is specified as a value between 0 to 2^24 - 1. If
Try this code. A complete version is given in the file
Do you understand why?
You have now learnt just enough to try writing a program to animate the Sieve of Eratosthenes. If you are feeling confident, you may go ahead and try to write it for yourself. You will need to combine the Sieve algorithm, from last week, with the graphical ideas from this week. Before you start writing your program, it's a good idea to write out the key steps in words:
It's a good idea to ask your program to take a pause between each step of the Sieve algorithm. You can do this with a statement like:
An example program is attached below
Check that you can run the example program