When this process is complete, the array elements that are still set to one indicate that the subscript is a prime number. These subscripts can then be printed. Write a program that uses an array of 1000 elements to determine and print the prime numbers between 2 and 999. Ignore element 0 of the array.

Question

(The Sieve of Eratosthenes) A prime integer is any integer that is evenly divisible only by itself and 1. The Sieve of Eratosthenes is a method of finding prime numbers. It operates as follows:
a) Create an array with all elements initialized to 1 (true). Array elements with prime subscripts will remain 1. All other array elements will eventually be set to zero. You’ll ignore elements 0 and 1 in this exercise.
b) Starting with array subscript 2, every time an array element is found whose value is 1, loop through the remainder of the array and set to zero every element whose subscript is a multiple of the subscript for the element with value 1. For array subscript 2, all elements beyond 2 in the array that are multiples of 2 will be set to zero (subscripts 4, 6, 8, 10, etc.); for array subscript 3, all elements beyond 3 in the array that are multiples of 3 will be set to zero (subscripts 6, 9, 12, 15, etc.); and so on.

Answer 1

```
#include
#include
using namespace std;

int main()
{
const int SIZE = 1000;
int array[ SIZE ];
int count = 0;

// set all array elements to 1
for ( int k = 0; k < SIZE; k++ )
array[ k ] = 1;

// test for multiples of current subscript
for ( int i = 1; i < SIZE; i++ )
{
if ( array[ i ] == 1 && i != 1 )
{
for ( int j = i; j < SIZE; j++ )
{
if ( j % i == 0 && j != i )
array[ j ] = 0;
} // end for
} // end if
} // end for

// display prime numbers
// range 2 - 197
for ( int q = 2; q < SIZE; q++ )
{
if ( array[ q ] == 1 )
{
cout << setw( 3 ) << q << " is a prime number.\n";
count++;
} // end if
} // end for
cout << "A total of " << count << " prime numbers were found." << endl;
} // end main
```
2 is a prime number.
3 is a prime number.
5 is a prime number.
7 is a prime number.
11 is a prime number.
13 is a prime number.
17 is a prime number.
19 is a prime number.
23 is a prime number.
29 is a prime number.
31 is a prime number.
...
929 is a prime number.
937 is a prime number.
941 is a prime number.
947 is a prime number.
953 is a prime number.
967 is a prime number.
971 is a prime number.
977 is a prime number.
983 is a prime number.
991 is a prime number.
997 is a prime number.
A total of 168 prime numbers were found.