Interactive Sieve of Eratosthenes

Named after the Greek Mathematician Erastosthenes, the sieve provides a very efficient method for finding prime numbers.

We start with a large grid of whole numbers. If we use the simple definition that a prime number is any number that has exactly 2 factors. Then we can eliminate 1 as not prime. The next number 2 is the first prime number, it also is uniquely the only even prime number.

Whenever a prime is found, we choose a color for example red and paint all of its multiples, so for 2 this would be 2,4,6,8 ...

Anything other than 2 that is painted red cannot be a prime number as it has more than two factors.(1,2 and the number itself). We now look for the next number that has not be colored, in this case 3. This is are next prime, You can use a different color to mark off its multiples 3,6,9,12 ...

The process is continued, look for the next number that has not been colored and paint its multiples. Eventually you will see only the prime numbers remaining.

Grid Sizes

Use the slider to change size from 2x2 up to 30x30, the really large squares can show how the method works also for larger numbers. Small grids can be used to examine the factors of a particular number (discussed below).

Colors

To select a particular color, click on it and to remove colors from the grid click on the white brush

The split color control when turned on it allows for a square to show more than one color.

Click the trash button to remove all colors from the grid

Modes

The activity has three different modes. In manual mode choose a color, then click and drag over the number squares to color them. In multiples mode, click a square and all it subsequent multiples will be automatically colored. The final automatic mode will run through the sieve, automatically allocating colors for each prime and its multiples. This can be useful for large numbers of squares, note press the start button to begin the process.

Animation Speed

Use the animation speed slider to change how fast multiples are highlighted

Using the Sieve

This activity has many different uses and can help explain many mathematical concepts apart from finding prime numbers.

Finding the Lowest/Least Common Multiple (LCM)

This example will work fine with the 100 squares or less, press trash to clear the grid, select multiples mode and make sure split color is on. So an example problem would be find the LCM of 4,6. To do this click the red paint icon, and click number 4 in the grid, all the multiples of 4 are now red. Click the yellow paint and then click the number 6, all the muliples of 6 will be shown as yellow. You should see the common multiples are colored boy red and yellow, these are 12,24,36 ... the LCM the least/lowest of the these is 12.

You can do this for more than two numbers, just make sure you use a different color for each one of the multiples you are using.

Finding the factors of a number

Like the LCM example, the default settings are used, multiples mode and split colors.

It is important to understand the relationship between factors and multiples. For example if 12 is one of the multiples of 4 then we know that 4 must be a factor of 12. So using the grid if I wanted to test if 5 is a factor of 15, then I can click trash to clear the grid and then choose a color and click on 5 to show all its multiples. If one of them is 15 then we know that 5 is indeed a factor of 15. To test if 4 is a factor of 15 you can either clear the grid or select a different color and then click 4, in this case the color does not hit 15 and so we know it is not a factor.

If you are only interested in the number upto 16, it is possible to select the 4x4 grid and assign a different color for each number 1-16. In this way the number of colors on each number, gives its number of factors

Prime factors class exercise

This is a whole class activity, as it can help students understand how each number can be expressed as a product of prime numbers. Start with a 100 square, split colors and automatic mode, click start to run through the sieve. When complete the primes have a single border color, and the composite numbers have one or more solid colors. These colors tell which prime factors the number has. So for example number 60 has 3 colors: red, yellow and lime. Look at the primes that represent these colors, red is 2, yellow is 3 and lime is 5. In this case 60=2×2×3×5

A question for the class would be what is special about the numbers that are not prime but only have a single color. Hopefully they can work out that these numbers only have one prime factor, so examples would be all the square numbers, all the cube numbers or in fact any number that can be expressed as an where a is a prime number and n is a positive integer.

Divisibility Tests

These grids can also be a good starting place for a discussion on division tests

So for example, any number that is divisibly by 2, must be a multiple of 2. So look at these numbers on the grid and hopefully the students can identify these numbers always end in 0,2,4,6 or 8. Other tests can also be investigated.


Related activities

The number explorer is also a useful teaching tool for factors, multiples and primes.

Set the size of the square
Set the mode, manual paint, multiples - show multiples of number, Automatic runs sieve.
Toggle split colors, when turned on more than one color can be shown on a square.
Set the animation speed.
Start
Click to find the primes in the grid
Trash resets the grid so all squares are off
Toggle audio on or off
Click to view instruction videos Close the activity View information about the activity Pan and zoom (using mouse/mousewheel)