Odlyzko [O1993] has a method for computing π(x) in time/space x1 / 2 + o(1); combining this with a binary search, one can locate a k-digit prime in time/space (10k)1 / 2 + o(1).
First observe that it suffices to compute π(x) to accuracy 1/2, since it is an integer. Next, it suffices to count the slight variant sum up to this accuracy, since the error term is a sum over prime powers and this can be computed in x1 / 2 + o(1) time/space (using e.g. the sieve of Eratosthenes to find all the primes up to x1 / 2).
In fact, it suffices to compute the sum
where c is a computable function which equals 1 for n < x − x1 / 2, vanishes for n > x, and is smooth in between. This is because the error can be computed in x1 / 2 + o(1) time/space via another sieve of Erathosthenes. [Actually, by using Odlyzko's method recursively, one can reduce this portion of the cost to x1 / 4 + o(1).]
The expression (1) can be rewritten using the zeta function as
It turns out that F is rapidly decreasing when , so to get within accuracy 1/2, one only needs to evaluate the integral for s = O(x1 / 2 + o(1)). By quadrature, this reduces to evaluating ζ(s) (and its first few derivatives) to accuracy about O(x − 1 / 2 + o(1)) for about x1 / 2 + o(1) values of s in this range, but this can be done in many ways (e.g. by the Euler-Maclaurin formulae).