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.
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/
Thank you so much, you have answered all my questions and then some, so thank you.
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.
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.)
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