Interactive Sieve of Eratosthenes
Named after the Greek mathematician Eratosthenes, the sieve provides an efficient method for finding prime numbers.
The process starts with a grid of whole numbers. Using the definition that a prime number has exactly two factors, we can eliminate 1. The next number, 2, is the first prime and is also the only even prime number.
When a prime is found, we use a color (e.g., red) to mark all of its multiples (2, 4, 6, 8, etc.). Any number marked this way cannot be prime because it has more than two factors (1, the prime number, and itself). We then find the next unmarked number, which is our next prime (in this case, 3), and use a different color to mark all of its multiples.
This process continues: find the next uncolored number and paint its multiples. Eventually, only the prime numbers will remain uncolored.
Grid Size
Use the slider to change the grid size from 2x2 up to 30x30. Larger grids can demonstrate how the method scales for finding larger primes, while smaller grids are useful for examining the factors of a specific number.
Colors
To select a color, click its icon. To deselect a color, click the white brush. The split color control, when enabled, allows a single square to display multiple colors if it is a multiple of several numbers. Click the trash button to remove all colors from the grid.
Modes
The activity has three different modes:
- Manual Mode: Choose a color, then click and drag over the number squares to color them freely.
- Multiples Mode: Click a square, and all of its subsequent multiples will be colored automatically.
- Automatic Mode: This mode automatically runs the Sieve of Eratosthenes, assigning colors for each prime and its multiples. Press the start button to begin the process.
Animation Speed
Use the animation speed slider to change how quickly the multiples are highlighted.
Applications of the Sieve
This activity can help explain many mathematical concepts beyond just finding prime numbers.
Finding the Least Common Multiple (LCM)
To find the LCM of 4 and 6, first clear the grid and select Multiples Mode with Split Color turned on.
- Select red paint and click on the number 4. All multiples of 4 will turn red.
- Select yellow paint and click on the number 6. All multiples of 6 will turn yellow. The common multiples (12, 24, 36, etc.) will be colored with both red and yellow. The smallest of these is 12, which is the LCM.
Finding the Factors of a Number
This tool also illustrates the relationship between factors and multiples. For example, to test if 5 is a factor of 15, clear the grid, choose a color, and click on 5 to show all its multiples. Since 15 is highlighted, 5 is a factor of 15. If you then click on 4, you will see that its sequence of multiples does not include 15, so 4 is not a factor.
Prime Factors Class Exercise
This is a great whole-class activity for understanding prime factorization. Start with a 100-square grid in Automatic Mode with Split Colors on. Run the sieve. When complete, the prime numbers will have a single border color, while composite numbers will be filled with the colors of their prime factors. For example, the number 60 will have three colors: red (for prime 2), yellow (for 3), and lime (for 5), showing that its prime factorization is 2×2×3×5.
A good question for the class: “What is special about the composite numbers that only have a single color?” (Answer: They are powers of a single prime number, e.g., 4, 8, 9, 16, 25, 27).
Divisibility Tests
The colored grids provide a good starting point for discussing divisibility tests. For example, by highlighting all multiples of 2, students can easily see that all divisible-by-2 numbers end in 0, 2, 4, 6, or 8. Other tests can be investigated in a similar visual way.
Related activities
The number explorer is also a useful teaching tool for factors, multiples, and primes.