The Sieve of Eratosthenes is an algorithm for calculating prime numbers which works by deleting composite numbers. For an interactive demonstration of this algorithm, see the IntegerZone.

It is possible to do the Sieve without any computer at all, just by writing the numbers down on paper:

• Write down the numbers from 2 to however far you want to go.
• Start with 2. Circle it, and then cross out all its multiples greater than itself.
• Go to the next uncrossed out number, which is 3. Circle it, and then cross out all its multiples greater than itself.
• And so on.

There is an interesting variant of this which involves distributed processing. You can do it in a classroom, with each student as a single processor.

First you need cards or papers, with each number from 2 up to some number N written on the card. Mark a line at the bottom of each card so that numbers like 6, 9, 16 etc don't get confused with their upside down versions.

Form all but one of the students into a line. They can be sitting down. The remaining student stands at the end with all the cards in order, ready to pass them on. This student passes each card onto the first member of the line.

Each member of the line obeys the following rules:

• If you have not yet received a card, hold on to the card (so that others can see what it is).
• If you are already holding a card, then see if the new card is a multiple of the card you are holding. If it is a multiple, discard it in front of you. If it is not a multiple, pass it further along the line.

All the cards that are held on to will be primes. After a while some cards will start reaching the end of the line. The sieve can continue until the square of the last prime held by a student is reached, and all numbers up to that point that reach the end of the line are also primes.

Of course it may be useful to reserve a few students to act as monitors – to watch the others and catch them if they make any mistakes.