In the third century B.C., the Greek astronomer Eratosthenes developed an algorithm for finding all the prime numbers up to some upper limit N. To apply the algorithm, you start by writing down a list of the integers between 2 and N. For example, if N were 30, you would begin by writing down the following list:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
You then begin by highlighting the first number on the list, indicating that you have found a prime. You then go through the rest of the list and blank out every multiple of the value you have just highlighted, since none of these muliples can be prime. Thus, after executing the first step of the algorithm, you will have highlighted number 2 and blanked out every multiple of two, as follows:
2
3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
From here, you simply repeat the process by highlighting the first number in the list that is neither blanked out or highlighted, and then crossing off its multiples, In the example, you would highlight 3 as a prime and blank out all multiples of 3 in the rest of the list, including those already blanked out, which would result in the following state:
2 3
4 5 6 7 8 9 10 11
12 13 14 15 16 17 18 19 20 21 22 23 24
25 26 27 28 29 30
Eventually, every number in the list will either be highlighted or blanked out, as shown in this diagram:
2 3
4
5
6
7
8 9 10
11
12
13
14 15 16
17
18
19
20 21 22
23
24 25 26 27 28
29
30
The highlighted numbers are the primes; the blanked-out numbers are composites. This algorithm for generating a list of primes is called the sieve of Eratosthenes.
Write a program that uses the sieve of Eratosthenes to generate a list of primes between 2 and 1000. The easiest approach is to store the numbers in an array in positions 2 to 1000, and blank out values by setting them to zero. The main process is then to sequentially step through the array searching for non-blanked-out values, and using them to blank out their multiples.
Note: with proper for loops, blanking out multiples is not a process of checking remainders, but simply using a proper step size in the for loop. For example, to blank out the multiples of 3, starting with 3 squared, use
Hand in the well-documented program and a sample run showing the primes.