The Sieve of Eratosthenes

You can find all the prime numbers very quickly by using a strategy called
The Sieve of Eratosthenes.

You use an array and nested loops to do this.

First declare an array of int for 10000 elements.

Put 0 into all the places (should automatically put in 0's but check)

Put 1's into all the multiples of 2 -  a[4] a[6] a[8] etc. (Note not a[2])
Put 1's into all the multiples of 3 - a[6] a[9] a[12] etc.  (Note not a[3])
You don't have to put 1's into multiples of 4 since a[4] is already 1
Put 1's into all the multiples of 5 - a[10] a[15] a[20] etc.  (Note not a[5])
Continue this until you reach 1/2 the array size.


When you are done - go through the array and anywhere you find a 0
print out that subscript.

Since a[1] is holding a 0 print out the 1.
Since a[2] is holding a 0 print out the 2.
Since a[3] is holding a 0 print out the 3.
Since a[4] is holding a 1 do not print out the 4.


Make your own free website on Tripod.com