HP Integrity NonStop H-Series - Manual (Page 64)

Click on the banner to return to the user guide home page.
©Copyright 1996 Rogue Wave Software
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 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;
}