// Program: eratosthenes4.C
// Calculate prime numbers in {2,...,n-1} using
// Eratosthenes' sieve.
#include
#include "array.C"
int main()
{
// input of n
std::cout << "Compute prime numbers in [2,n) for n =? ";
unsigned int n;
std::cin >> n;
// definition and initialization: provides us with
// Booleans crossed_out[0],..., crossed_out[n-1]
array crossed_out (n);
for (unsigned int i = 0; i < 1000; ++i)
crossed_out[i] = false;
// computation and output
std::cout << "Prime numbers in [0," << n << "): ";
for (unsigned int i = 2; i < n; ++i)
if (!crossed_out[i]) {
// i is prime
std::cout << i << " ";
// cross out all proper multiples of i
for (unsigned int m = 2*i; m < n; m += i)
crossed_out[m] = true;
}
std::cout << "\n";
return 0;
}