### How to make sieve of eratosthenes more efficient?

 ``12345678910111213141516171819202122232425262728293031323334353637383940`` `````` const long long primesupto=20000000; vector primesarr(primesupto); ofstream primesout("primes.txt"); for (int load=0;loadprimesupto) break; primesarr [(p2 *p1)-1]=0; } } } long long int nthprime=0; for (int p3=0;p3

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?
Last edited on
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.
Topic archived. No new replies allowed.