a sieve

sieve.cpp

#include <sstream>
#include <iostream>
#include <numeric>
#include <cmath>
#include <vector>
#include <list>
#include <iterator>
using namespace std;

/**
   primes.

@author james northrup
*/
int main(int argc,const char**argv) {
    unsigned  num=25000;
    if (argc>1) {
        stringstream par(argv[1]);
        par >> num;
    }

    vector<unsigned>backbone;
    list<unsigned>mouth;

    back_insert_iterator<vector<unsigned> >cocyx (backbone);
    back_insert_iterator<list<unsigned> > chomp(mouth);
    chomp=2;
    unsigned counter=1;

    for (unsigned i = 3; counter <  num; i+=2) {
        unsigned srti=sqrt(i) ;
        bool prime = true;
        unsigned f;
        while (!mouth.empty()&&(srti>=(f=mouth.front()))) {
            mouth.pop_front();
            cocyx=f;
        }

        for (vector<unsigned>::iterator iter=backbone.begin(); prime&&backbone.end()!=iter;++iter)  {
            if ( 0==(i %  *iter ) ) {
                prime = false;
            }
        }
        if (prime) {
            chomp=i;
            counter++;
        }
    }

    cout << "primes[ " << counter << "] is " <<  mouth.back()<<endl;
    // visual c++ convenience
    // cin >> ret;
    return 0;
}

g++ -O7 sieve.cpp &&time ./a.out
primes[ 25000] is 287117

real 0m0.019s
user 0m0.010s
sys 0m0.000s