﻿ Sieve of Eratosthenes | Mathematics | Computing ﻿

# Sieve of Eratosthenes

Can you use this ancient Greek method to identify prime numbers? Clicking on a number will cycle through the colours; right-clicking will cycle through in reverse order.

Click to shade and find multiples yourself or press S or tap with two fingers to shade multiples.

Starting at the top left, move to the next uncoloured square and colour the squares containing multiples of the number in the square (but not the number itself - e.g. move to square 2 and shade 4, 6, 8, etc, then move to square 3 and shade 6, 9, 12, etc.).  Repeat until there are no further uncoloured squares as far as the square root of the largest number in the grid.

The Sieve of Eratosthenes works by excluding known multiples - remove (by colouring) the multiples of 2, 3, 4, etc., until there are no multiples left. The remaining, uncoloured, squares contain prime numbers.  For finding sets of prime numbers, this is a more efficient solution than checking all of the numbers individually to see if they are prime.

By default the grid shows numbers up to one hundred and multiples are removed every two seconds, but the this can be changed using the ?max and ?freq querystrings and giving a period in milliseconds.  For example, to have numbers up to fifty and exclude a multiple every second, add ?max=50&freq=1000 to the end of the URL.