What is the time complexity of generating n-th prime number?

Problem Detail: 

Say I want to find the n-th prime. Is there an algorithm to directly calculate it or must I do with sieving? I know always calculate the next prime with a sieve principle, but what if I want the n-th prime?

Duplicate:

http://math.stackexchange.com/questions/1257/is-there-a-known-mathematical-equation-to-find-the-nth-prime

Asked By : Dac Saunders

Answered By : Kaveh

What do you mean by "directly"? This is not well-defined. Arguing that an algorithm doesn't do something during its computation is not a nice well-defined concept (when that something is a semantic condition).

It is probably one of the most common mistakes that people make when thinking about algorithms because they look at obvious cases and think it is simple to formalize the concept that algorithms for a problem does performs some task like computing some other things during its computation but that is not simple at all!

Moreover why would we care? What we care about in practice is not that the algorithm computes all previous primes, but rather time and space efficiency. So I guess a better way of asking your question is asking if there is more efficient way of computing $n$th prime number than sieve-based methods.

If you are asking if there is a provably correct and efficient algorithm to find $n$th prime given $n$ in binary the answer is that is an open question. We don't know if there is any such algorithm, and we don't know if there isn't one. AFAIK, it is consistent with our current state of knowledge that there are algorithms for generating the $n$th prime that run in linear time in $n$. In fact, it can even be the case that we can generate the $n$th prime from bits of $n$ using a polynomial-size constant-depth circuit with threshold gates ($\mathsf{TC^0}$), in simplified non-technical terms: there can be a parallel algorithm with polynomial number of processors that generates the $n$th prime number in constant time and each processor computes very simple functions. So there is big gap between algorithms that we have (upper-bounds) and lower-bounds we can prove for the problem.

However we have algorithms that work efficiently and correctly assuming conjectures like conjectures about how primes are distributed.

See the Wikipedia article on generating prime numbers if you haven't. Also you may want to check this question: Which is the fastest algorithm to find prime numbers?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10683