Sieve of Eratosthenes algorithm

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,"\n"));

}

I have no idea why you're not getting all the output, as it looks like you should get everything. What output are you missing?

The sieve is implemented wrongly. Something like

vector<int> sieve;
vector<int> primes;

for (int i = 1; i < max + 1; ++i)
   sieve.push_back(i);   // you'll learn more efficient ways to handle this later
sieve[0]=0;
for (int i = 2; i < max + 1; ++i) {   // there are lots of brace styles, this is mine
   if (sieve[i-1] != 0) {
      primes.push_back(sieve[i-1]);
      for (int j = 2 * sieve[i-1]; j < max + 1; j += sieve[i-1]) {
          sieve[j-1] = 0;
      }
   }
}

would implement the sieve. (Code above written off the top of my head; not guaranteed to work or even compile. I don't think it's got anything not covered by the end of chapter 4.)

Return primes as usual, and print out the entire contents.

From Algorithms and Data Structures:

void runEratosthenesSieve(int upperBound) {
      int upperBoundSquareRoot = (int)sqrt((double)upperBound);
      bool *isComposite = new bool[upperBound + 1];
      memset(isComposite, 0, sizeof(bool) * (upperBound + 1));
      for (int m = 2; m <= upperBoundSquareRoot; m++) {
            if (!isComposite[m]) {
                  cout << m << " ";
                  for (int k = m * m; k <= upperBound; k += m)
                        isComposite[k] = true;
            }
      }
      for (int m = upperBoundSquareRoot; m <= upperBound; m++)
            if (!isComposite[m])
                  cout << m << " ";
      delete [] isComposite;
}