Hints on the Eratostenes program

This is a very efficient method to find all the prime numbers from 2 to 999. In this example, I'll use 20, not 999.

Prime numbers are positive integers that can not be divided by any number except 1 and itself (without remainder).

You'll need an array with indices from 1 to 999. Because element numbering always start with zero in C, you will need an array with 1000 elements. In this array, you mark for each number whether you have already eliminated it as a possible prime number.

Step 1: initialize all array elements to unmarked (e.g., 1)

array indices 01234567891011121314151617181920
array elements 111111111111111111111

Step 2: Start with the number 2. 2 is defined to be the smallest prime number. Print it out, since it is not marked. Then, mark all multiples of 2 (you know they are not prime numbers). Mark them with 0, for example.

array indices 01234567891011121314151617181920
array elements 111101010101010101010

Step 3: Number 3. Print it out, since it is not marked. That means it is a prime number. Then, mark all multiples of 3 (6, 9, 12, 15, 18,...). (Some of them will already be marked, but you don't care.)

array indices 01234567891011121314151617181920
array elements 111101010001010001010

Step 4: Number 4. It is marked, so it is not a prime number. Don't print it out. All multiples of 4 are already marked (because they are also multiples of 2), so you don't have to do anything else.

Step 5: Number 5. Unmarked -> it is prime -> print it out. Mark all multiples of 5.

Step 6: Number 6. Same as for number 4.

Step 7: Number 7. Unmarked -> it is prime -> print it out. Mark all multiples of 7.

And so on!

In order to test your program, it is a good idea to write a function that prints out the entire array, i.e. for each array element, it prints the array index and the array element.