How to find nth prime with complexity o(1)

How to find nth prime num开发者_如何转开发ber with complexity o(1)

The only way to do this in O(1) would be an array of all prime numbers. So, you'd only be able to support a certain number depending on your computer's memory.

Edit:

There might be some way to compute this involving a bunch of calculus, but that's beyond me :)

You can't. In fact, you can't enumerate prime number without doing exhaustive search.

If you have a database with all prime numbers up to n you could search the nth prime number (up to n) in o(log n).

To find the n-th prime in fixed time would imply that there's a reasonable formula for calculating pi(n) (return the n-th prime number). See http://primes.utm.edu/notes/faq/p_n.html for preliminary discussion on this topic.