Trouble with the Sieve of Eratosthenes in C++

Question

I'm trying to implement the Sieve of Erasthones in C++, and I've run into lots of problems. My code is as follows:

#include <iostream>
int main()
{
    const int max = 1000;
    int count = 1;
    bool arr[max];

    for(int i = 0; i < max; ++i)
        arr[i] = true;

    for(int i = 2; i < max; i++)
    {
        //mark all multiples
        for(int j = 2; (j*i) < max-1; ++j) arr[i*j] = false;
    }
}

I don't know what the next step is. I've looked online but I don't understand a lot of the code. Can you please provide an example of working c++ code and how it works?

Answer 1

There's no major flaw in your code - it works, but it's a bit bulky.

The basic logic is:

1. Fill a vector, named sieve, with 1s (chars to save memory)
2. For each prime element in the first vector, mark all of its multiples as prime
3. Add every prime element int he first vector the the retVector, and return the vector of all primes up until limit

Another working implementation of the sieve in c++ might look something like the following:

vector<long long> sieve(unsigned long long & limit) 
{
    vector<char> sieve(limit, '1');
    vector<long long> retVector;

    for (long long i = 0; i < limit; i++)
        sieve[i] = 1;

    for (long long i = 2; i < limit; i++) {
        if (sieve[i] == 1) {
            for (long long j = i*i; j < limit; j += i)
                sieve[j] = 0;
        }
    }
    for (long long i = 2; i < limit; ++i) if (sieve[i] == 1) retVector.push_back(i);
    return retVector;
}

Answer 2

There's nothing really wrong with your code - it actually works. It's not the best implementation, but it's a good start if you have little to no experience coding, so congratulations!

To see that your code works, simply add another loop that prints the prime numbers:

int main()
{
    const int max = 1000;
    int count = 1;
    bool arr[max];

    for(int i = 0; i < max; ++i)
        arr[i] = true;

    for(int i = 2; i < max; i++)
    {
        //mark all multiples
        for(int j = 2; (j*i) < max-1; ++j) arr[i*j] = false;
    }

    for (int i = 2; i < max; ++i)
        if (arr[i])
            cout << i << " ";
}

What your code does:

• It initializes an array arr of size max which, at the end of the execution of your algorithm, will have arr[i] == true if i is a prime number and arr[i] == false otherwise;

• Your algorithm works by first assuming that each number is prime. Then, it starts correcting this assumption by setting the multiples of each number 2, 3, 4, 5, 6, ... as not being prime numbers: this is correct, because any multiple of any number other than 1 cannot be prime (as it will be divisible by that number).

Your code and algorithm can be improved in a variety of ways:

• Only mark multiples of prime numbers as not being prime, because the other will have already been marked previously. This will make your program more efficient;

• Improve the memory usage by using a bitset;

• Start marking off multiples from the squares of primes;

• Treat 2 as an edge case, since it is the only even prime. Then you can start iterating numbers starting from 3 and going in increments of 2: 3, 5, 7, 9, ....