The aim of this program is to assign to a[i] the value 1 if i is a prime number and the value 0 if not. Initially, all elements of the array take the value 1 to indicate that there are no numbers which are known not to be prime. Then all elements of the array corresponding to indexes that are known not to be primes (multiples of known primes) take the value 0. If a[i] has the value 1 even after all multiples of smaller primes have taken the value 0, we know that i is a prime number.

Because the program uses an array whose elements are of the simplest type (values 0 and 1), we would save space if we used an explicit array of digits, not a list of integers. Also, some programming environments may require the array declared as global variable if N is large, although we could allocate memory for the array dynamically.

You should know that the implementation of the algorithm does not take into account issues of data input validation or proper management of dynamic memory (e.g. avoiding memory leaks) because it is only necessary to highlight the logic of the algorithm.

#include <iomanip>
#include <iostream>
using namespace std;

const int N = 1000;

int
main () {
  int i, a[N];

  cout << setw (5) << setfill ('0') << "1" << endl;

  for (i = 2; i < N; i++) a[i] = 1;

  for (i = 2; i < N; i++)
    if (a[i])
      for (int j = i; j*i < N; j++)
        a[i*j] = 0;

  for (i = 2; i < N; i++)
    if (a[i])
      cout << setw (5) << setfill ('0') << i << endl;

  return 0;
}