5.4 Example Program - Sieve of Eratosthenes

Click on the banner to return to the user guide home page.

5.4 Example Program - Sieve of Eratosthenes

Obtaining the Source

An example program that illustrates the use of vectors is the classic algorithm, called the sieve of Eratosthenes, used to discover prime numbers. A list of all the numbers up to some bound is represented by an integer vector. The basic idea is to strike out (set to zero) all those values that cannot be primes; thus all the remaining values will be the prime numbers. To do this, a loop examines each value in turn, and for those that are set to one (and thus have not yet been excluded from the set of candidate primes) strikes out all multiples of the number. When the outermost loop is finished, all remaining prime values have been discovered. The program is as follows:

void main() {
      // create a sieve of integers, initially set
   const int sievesize = 100;
   vector<int> sieve(sievesize, 1);

      // now search for 1 bit positions
   for (int i = 2; i * i < sievesize; i++)
      if (sieve[i])
         for (int j = i + i; j < sievesize; j += i)
            sieve[j] = 0;

      // finally, output the values that are set
   for (int j = 2; j < sievesize; j++)
      if (sieve[j])
         cout << j << " ";
   cout << endl;
}