# Sieve of Eratosthenes

Copyright © 2006 Philip Dorrell

with numbers from 1 to

### HINTS:

- To change the number of cells per row, resize your browser window.
- To see more numbers at once, choose a smaller text size in the browser menu.
- Use the "Reduce cell width" button if the number cells are wider than they need to be.
- Use the "Increase cell width" button if the numbers don't fit in the cells, or if the cells are uneven sizes.
- This page depends on CSS (Cascading Style Sheets) and Javascript. By default these will be switched on in your browser, but if you have switched them off, then the page will not work. If Javascript is off, then you won't see any numbers at all. If CSS is off, you will see them, but they won't be in a grid. (Most browsers allow Javascript to be turned off, and Mozilla Firefox lets you turn off styles via the menu option "Page Style":"No Style".)
- The page has been tested on the latest versions of Internet Explorer (6.0.2900), Mozilla Firefox (1.5.0.1) and Opera (8.52) running on Windows XP.
- You can choose a different range of numbers to sieve on. However, if you choose too large a range, the response of the program becomes very slow (depending to some extent on the choice of web browser).

### THE MATH:

A prime number is a natural number (i.e. a non-negative whole number) greater than 1 which has no factors other than itself and 1. A composite number is a number greater than 1 which does have factors other than 1 and itself, i.e. a composite number is a number greater than 1 which is not a prime number.

One way to find out which numbers are prime is to check each number and see if it is a multiple of any number between 1 and itself. However, it is easy to show that every composite number must have at least one prime factor less than itself, so you only need to check if it is a multiple of a prime number between 1 and itself. The Sieve of Eratosthenes (invented by the ancient Greek mathematician Eratosthenes) reverses this checking procedure by iterating over the primes and eliminating all multiples of each prime. Whatever numbers are left over must be primes.

Two slightly tricky things about this process are (1) you have to decide in advance the maximum size of numbers to eliminate (because every prime has an infinite number of multiples) and (2) the algorithm is consuming prime numbers (when it eliminates the multiples) and producing them (as revealed by which numbers are not eliminated) at the same time, so maybe the consumption might get ahead of the production.

The first issue is dealt with by deciding how many numbers to apply the algorithm to in advance (this program defaults to 100, but you can try larger). The second issue turns out not to be a problem, because if you eliminate multiples of primes in the order that the primes occur, the next uneliminated number must always be a prime (since you have already found that no prime number smaller than it is a factor). Indeed, once the multiples of a prime and all primes less than it have been eliminated, you know that all uneliminated numbers less than the square of that prime must be prime numbers. So the production always keeps safely ahead of the consumption.

Back to Math Activities