Created
June 30, 2012 08:27
-
-
Save jnorthrup/3022945 to your computer and use it in GitHub Desktop.
a sieve
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
g++ -O7 sieve.cpp &&time ./a.out
primes[ 25000] is 287117
real 0m0.019s
user 0m0.010s
sys 0m0.000s