Fastest Nth Prime Algorithim

[da peppester]

Whats the fastest way to get the Nth prime number? There can be no gapes what-so-ever, and N can be as big as a few million-ishy (maybe even a billion or two in rare circumstances). The reason I want to know if there is an algorithm that can do this is because I have found a real genuine practical usage for an Nth prime number algorithm that is not for using it to post a massive prime number it up on a website to say: look at what I can do.

[helios]

The fastest method would probably be using a sieve. A sieve large enough to find the two billionth prime would probably require around 6 GiB of memory (estimated using the prime number theorem).

[48T7M4Gy]

http://stackoverflow.com/questions/453793/which-is-the-fastest-algorithm-to-find-prime-numbers

[da peppester]

Thank you so much, abut is there is more efficient way to extract the nth prime without calculating all the previous like sieve does?

[helios]

I don't think so.
The good news is that once you have the complete sieve, you can save the results in a table and reuse them.

[JLBorges]

Wheel factorisation would significantly reduce the number of computations.

Notice that the simple wheel based on 2 and 3 removed 4/6 = 2/3 rds of the composites. The larger wheel using 2, 3, 5, and 7 will remove 162/210 (over 77%) of the composites.
http://primes.utm.edu/glossary/page.php?sort=WheelFactorization

A segmented sieve implementation would reduce memory requirements and would be much faster (better cache locality). https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Segmented_sieve

primesieve generates primes using the segmented sieve of Eratosthenes with wheel factorization.
...
primesieve generates primes about 50 times faster (single-threaded) than an ordinary C/C++ sieve of Eratosthenes implementation ... and also substantially outperforms primegen the fastest sieve of Atkin implementation on the web.
http://primesieve.org/

[da peppester]

Thank you so much, you have answered all my questions and then some, so thank you.

@Helios
Also.... for the purposes of what I will be using this for, I just don't have the memory to store the results in a quick-cache table. And, I will be distributing this which means I am morally obligated not to abuse the disk.

[helios]

Store them in a file. 15 GiB should be enough to store the first two billion primes.

[48T7M4Gy]

Is it another Project Euler?

Could be and if it is PE you don't need much memory and long int will more than suffice for PE problems of prime number concern IIRC.

With the algorithm for Eratosthenes Sieve from Wikipedia it's all done complete with storage along the way in a couple of milliseconds up to the range of long int. Try the wheel, try segment sieves, they all sound quicker.

(A lot less than 2 billion primes occur in the range of long int of course.)

[helios]

The second billionth prime is actually only a bit larger than 47 billion.

https://primes.utm.edu/nthprime/index.php

[48T7M4Gy]

The 2,000,000,000th prime is 47,055,833,459

and

ULONG_MAX Maximum value for a variable of type unsigned long. 4,294,967,295 (0xffffffff)

(A lot less than 2 billion primes occur in the range of long int of course.)

that was a lucky guess.

[helios]

I thought you were talking about 64-bit values.

In any case, long doesn't have a defined size, although it's guaranteed to be at least 32 bits long.

[48T7M4Gy]

Well, that could be right and was something I quickly thought about and left to just cut and paste from the Microsoft website. I must admit I was more focussed on not being picked up on the unsigned nature of the number and relied on their comment at the top of the table re limits.h

https://msdn.microsoft.com/en-AU/library/296az74e.aspx

_UI64_MAX Maximum value for a variable of type unsigned __int64 18446744073709551615 (0xffffffffffffffff)

a different game altogether