How to correctly implement the Sieve of Eratosthenes to find primes in C++?

by Daniel Barker   Last Updated May 15, 2019 17:26 PM

[This is not homework, it's self study]

I'm trying to make a program that uses the Sieve of Eratosthenes to find all the prime numbers from 1 to a user-selected max-value, and I don't really understand the inner increments, like how to eliminate all values that are multiples of previous primes. Could someone please look at my code, and explain to me the correct way to fix what I've got, so that I can understand it? Thanks

#include "../std_lib_facilities_revised.h"

int main()
{
    // 0 represents false
    // 1 represents true
    int max = 0;
    cout << "Enter a max value (greater than or equal to 0) for the Sieve of Eratosthenes:\n";
    cin >> max;
    cout << "Max is: " << max << '\n';
    vector<int> table(max + 1);
    cout << "table size: " << table.size() << '\n';
    table[0] = 0;
    table[1] = 0;
    for (int i = 2; i < max + 1; ++i) {
        table[i] = 1;
    }

    // print the table
    cout << "table after initialization:\n";
    for (int i = 0; i < table.size(); ++i) { 
        cout << table[i] << '\n';
    }

    for (int i = 2; i < max + 1; ++i) {
        if (table[i] == 1) {
            for (int j = i; j < max + 1; j += i) {
                table[j] = 0;
            }
        }
    }

    // print the table after marking primes
    cout << "table after marking primes:\n";
    for (int i = 0; i < table.size(); ++i) {
        cout << table[i] << '\n';
    }

    for (int m = 0; m < max + 1; ++m) {
        if (table[m] == 1) {
            cout << m << '\n';
        }
    }
}
Tags : c++


Related Questions