run the sieve out to a value larger than N, say 10 times as many (you can look it up, but I believe the rule of thumb is 10% of numbers are prime over a large N)
but you can stop when your marker value is > Nth one!
so if you need the first 10 primes,
you do 1 to 100
you find 2,3,5,7,11,13 //13 is the 6th ...
Hey, you found the 10th one! you don't need to iterate 29, you can stop right there.
start there. you can add some tweaks -- even a lookup table of some values for N vs the Nth prime, eg 10 is 29 .. and use the lookup table to estimate a better stopping point than 10N
you know that the nth prime is > N, so the trick is to estimate by how much, see if you can spot some sort of good approximation on that.
now if you are with me so far...
what happens if you only run 5 iterations of the sieve for each number? :) (it does not work, but is there some way to use the *idea* with some computed value to stop sooner?)
this will stop working after a while, I think. need a better way to get 'guesser'. But it works to at least 10k, as shown. Just a quick hack on some of the ideas I was throwing around.
vector<bool> p(1000000ull, true);
uint64_t numprimes = 10000;
uint64_t guesser = 11;
p = true; //seed 2 and the even values
for(int i = 4; i < numprimes * guesser; i+=2)
p[i] = false;
for(uint64_t i = 3; i < guesser*numprimes; i+=2)
uint64_t j = i<<1;
while(p[i] && j< numprimes*guesser)
p[j] = false;
int pcount = 0;
for(int i = 2; i < p.size() && pcount < numprimes; i++)
cout<< i << " ";
edit.. darn forum. Sorry about the indentation, it looked fine on my end...