# Odlyzko's method

Odlyzko [O1993] has a method for computing $\pi(x)$ in time/space $x^{1/2+o(1)}$; combining this with a binary search, one can locate a k-digit prime in time/space $(10^k)^{1/2+o(1)}$.

First observe that it suffices to compute $\pi(x)$ to accuracy 1/2, since it is an integer. Next, it suffices to count the slight variant sum $\sum_{n \leq x} \frac{\Lambda(n)}{\log n}$ up to this accuracy, since the error term is a sum over prime powers and this can be computed in $x^{1/2+o(1)}$ time/space (using e.g. the sieve of Eratosthenes to find all the primes up to $x^{1/2}$).

In fact, it suffices to compute the sum

$\sum_{n} c(n) \frac{\Lambda(n)}{\log n}$ (1)

where c is a computable function which equals 1 for $n \lt x - x^{1/2}$, vanishes for $n\gtx$, and is smooth in between. This is because the error can be computed in $x^{1/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 $x^{1/4+o(1)}$.]

The expression (1) can be rewritten using the zeta function as

$\frac{1}{2\pi i} \int_{2-i\infty}^{2+i\infty} F(s) \log \zeta(s)\ ds$

where

$c(u) = \frac{1}{2\pi i } \int_{2-i\infty}^{2+i\infty} F(s) u^{-s}\ du$.

It turns out that F is rapidly decreasing when $Im(s) \gg x^{1/2}$, so to get within accuracy 1/2, one only needs to evaluate the integral for $s = O(x^{1/2+o(1)})$. By quadrature, this reduces to evaluating $\zeta(s)$ (and its first few derivatives) to accuracy about $O(x^{-1/2+o(1)})$ for about $x^{1/2+o(1)}$ values of s in this range, but this can be done in many ways (e.g. by the Euler-Maclaurin formulae).