Find the first n prime numbers using the sieve of erathostenes

[Qsh222]

The program is supposed to display the first n prime numbers, where n is inputted by the user. I only managed to work out a really slow solution. Could someone help me write a quicker solution, that involves a sieve of eratosthenes. I'd know how to do this if the question asked for the prime numbers from 1 to n. But it's not the case.

[jonnin]

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 ...
17,19,23,29,
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.

int main()
{
   vector<bool> p(1000000ull, true);
   uint64_t numprimes = 10000;
   uint64_t guesser = 11;
   
   p[2] = 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;
		  j+=i;		  
		}	
	   		
	}
	int pcount = 0;
	 for(int i = 2; i < p.size() && pcount < numprimes; i++)
	 {
       if(p[i]) 
	   {
		 pcount ++;
         cout<< i << " ";		   
	   }	   
	 }		
}

edit.. darn forum. Sorry about the indentation, it looked fine on my end...

[JLBorges]

Use the prime number theorem to generate an upper bound on the nth prime number.
https://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number

const auto logn = std::log(n) ;
const std::size_t upper_bound = n * ( logn + std::log(logn) ) + 1 ;

Create a sieve up to the upper bound; use the sieve to generate n prime numbers.