// Program: eratosthenes2.cpp // Calculate prime numbers in {2,...,n-1} using // Eratosthenes' sieve. #include int main() { // input std::cout << "Compute prime numbers in {2,...,n-1} for n =? "; unsigned int n; std::cin >> n; // definition and initialization: provides us with // Booleans crossed_out[0],..., crossed_out[n-1] bool* const crossed_out = new bool[n]; // dynamic allocation for (unsigned int i = 0; i < n; ++i) crossed_out[i] = false; // computation and output std::cout << "Prime numbers in {2,...," << n-1 << "}:\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"; delete[] crossed_out; // free dynamic memory return 0; }