What's the most efficient algorithm for calculating an $nth$ prime, both deterministically and probabilistically?
Deterministic
- Iterate through only odd values, incrementing by $2$.
- Divide each value by $2 < divisor < \sqrt{value}$, where $divisor$ is only any one of the primes computed thus far.
- Any further optimization to be had, or should I resort to a sieve? If the latter, then which one?
Probabilistic
- Iterate through only odd values, incrementing by $2$.
- Use a probabilistic primality test, but which one?
Ultimately, after thorough optimization, will the deterministic or probabilistic approach yield greatest runtime efficiency? The algorithm's intended for execution by a computer.
For large $n$, your best bet is to estimate the $n$th prime number $x$ e.g. using http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number and then use sub-linear methods suggested by Daniel Fischer and others to calculate the exact number $\pi(x)$ of primes less than or equal to your estimate $x$ for the $n$th prime. Then you have a choice to make. Either you can zero in on the $n$th prime number using primality testing to go through candidates starting from your initial guess, or you can refine your estimate for the $n$th prime and recalculate the number of primes less than or equal to your estimate again. Considering that the given error for the $n$th prime number estimate given on the wikipedia link is $O(n / (\log n)^2)$, and that calculating $\pi(x)$ is about $O(x^{2/3})$ time or better, a good strategy is to essentially do a sort of binary search to refine your choice of $x$ so that $\pi(x)$ gets closer and closer to $n$, until the error between $\pi(x)$ and $n$, multiplied by the computational cost for primality testing for numbers about equal to $x$, is lower than the computational cost of computing $\pi(x)$ again. Then you do primality testing to zero in on the exact $n$th prime number.