math activities

Sieve of Eratosthenes

with numbers from 1 to


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.