c++ - Sieve of Eratosthenes algorithm

Question

I am currently reading "Programming: Principles and Practice Using C++", in Chapter 4 there is an exercise in which:

I need to make a program to calculate prime numbers between 1 and 100 using the Sieve of Eratosthenes algorithm.

This is the program I came up with:

#include <vector>
#include <iostream>

using namespace std;

//finds prime numbers using Sieve of Eratosthenes algorithm
vector<int> calc_primes(const int max);

int main()
{
    const int max = 100;

    vector<int> primes = calc_primes(max);

    for(int i = 0; i < primes.size(); i++)
    {
        if(primes[i] != 0)
            cout<<primes[i]<<endl;
    }

    return 0;
}

vector<int> calc_primes(const int max)
{
    vector<int> primes;

    for(int i = 2; i < max; i++)
    {
        primes.push_back(i);
    }

    for(int i = 0; i < primes.size(); i++)
    {
        if(!(primes[i] % 2) && primes[i] != 2)
             primes[i] = 0;
        else if(!(primes[i] % 3) && primes[i] != 3)
             primes[i]= 0;
        else if(!(primes[i] % 5) && primes[i] != 5)
             primes[i]= 0;
        else if(!(primes[i] % 7) && primes[i] != 7)
             primes[i]= 0;
    }   

    return primes;
}

Not the best or fastest, but I am still early in the book and don't know much about C++.

Now the problem, until max is not bigger than 500 all the values print on the console, if max > 500 not everything gets printed.

Am I doing something wrong?

P.S.: Also any constructive criticism would be greatly appreciated.

Answer 1

Think of the sieve as a set.
Go through the set in order. For each value in thesive remove all numbers that are divisable by it.

#include <set>
#include <algorithm>
#include <iterator>
#include <iostream>


typedef std::set<int>   Sieve;

int main()
{
    static int const max = 100;

    Sieve   sieve;

    for(int loop=2;loop < max;++loop)
    {
        sieve.insert(loop);
    }


    // A set is ordered.
    // So going from beginning to end will give all the values in order.
    for(Sieve::iterator loop = sieve.begin();loop != sieve.end();++loop)
    {
        // prime is the next item in the set
        // It has not been deleted so it must be prime.
        int             prime   = *loop;

        // deleter will iterate over all the items from
        // here to the end of the sieve and remove any
        // that are divisable be this prime.
        Sieve::iterator deleter = loop;
        ++deleter;

        while(deleter != sieve.end())
        {
            if (((*deleter) % prime) == 0)
            {
                // If it is exactly divasable then it is not a prime
                // So delete it from the sieve. Note the use of post
                // increment here. This increments deleter but returns
                // the old value to be used in the erase method.
                sieve.erase(deleter++);
            }
            else
            {
                // Otherwise just increment the deleter.
                ++deleter;
            }
        }
    }

    // This copies all the values left in the sieve to the output.
    // i.e. It prints all the primes.
    std::copy(sieve.begin(),sieve.end(),std::ostream_iterator<int>(std::cout,"
"));

}