The following is an example of the Sieve of Eratosthenes done almost entirely via the C++ Standard Template Library (STL). The common myth about the STL is that using any template whatsoever results in both code bloat and slow code. This is barking nonsense, as demonstrated by the following 100% ANSI C++ code.

I think you'll find the resulting code is tight, lean, and blindingly fast. For bonus points open it up and step through the Assembly code. It'll be an eye-opening experience in terseness.


/* Templatized Sieve of Eratosthenes by Robert J. Hansen
   <rjh@sixdemonbag.org>.  This code is donated to the 
   public domain, but attribution is always welcomed. */

#include <iostream>
#include <functional>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iterator>

using std::vector;
using std::remove_if;
using std::bind2nd;
using std::not2;
using std::modulus;
using std::copy;
using std::ostream_iterator;
using std::cout;

int main()
{
    vector<unsigned int> vec;
    const unsigned int UPTO = 1000000;
    const unsigned int stopAt = static_cast<unsigned int>(sqrt(static_cast<double>(UPTO)));
    vector<unsigned int>::iterator iter;
    
    vec.push_back(2);
    for (unsigned int i = 3 ; i < UPTO ; i += 2)
        vec.push_back(i);

    iter = vec.begin();
    while (*iter <= stopAt)
        vec.erase(remove_if
            (iter+1,
            vec.end(),
            bind2nd(not2(modulus<int>()), *iter++)),
            vec.end());

    copy(vec.begin(), vec.end(), ostream_iterator<unsigned int>(cout, " "));
    cout << "\n";
    
    return 0;
}