How to make sieve of eratosthenes more efficient?

[rozick1]

My implementation was this:

	const long long primesupto=20000000;
	
	vector<int> primesarr(primesupto);
	ofstream primesout("primes.txt");


	for (int load=0;load<primesupto;load++)
        primesarr[load]=1;

	

    for (int p1=2;p1<primesupto;p1++)
    {
        if (primesarr[p1-1]!=0)
        {

       	 for (int p2=2;p2<primesupto;p2++)
       	 {
        	    if ((p2*p1)>primesupto)
			break;

          	    primesarr [(p2 *p1)-1]=0;

       	 }
        }

    }
	long long int nthprime=0;

    for (int p3=0;p3<primesupto;p3++)
    {
	if (primesarr[p3] ==1 && nthprime<1000000)
	{
		primesout << p3+1<<endl; 
		nthprime++;
	} 
	
    }

The problem with this is that you have to start guessing how many numbers you'll need in the vector (I'm assuming that there isn't a formula for what number the nth prime is?). You also start using lots of RAM. Is there a way of avoiding these problems?

[Veltas]

If you want a specific prime then you should use a direct approach like trial division.

http://en.wikipedia.org/wiki/Prime#Trial_division

A prime sieve is the fastest way of generating all the primes in a range. The memory complexity is a real issue (how much memory you need to find a certain number of primes) but it can be seriously reduced by only creating smaller arrays (or vectors) of integers before sieving from them and discarding these smaller arrays before moving onto the next sub-range.

Before even doing this, however, immediately I could suggest that you:
1. Don't bother initialising each element of primesarr in a loop; use the
2. Use a bool, not an int, to store primesarr's elements. Use true and false rather than 1 and 0.
3. You only need to go up to sqrt(primesupto) in your main for loop to cover all primes in that range.