# Odlyzko's method

### From Polymath1Wiki

Odlyzko [O1993] has a method for computing π(*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 π(*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 *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

- (1)

where c is a computable function which equals 1 for *n* < *x* − *x*^{1 / 2}, vanishes for *n* > *x*, 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

where

- .

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*(*x*^{1 / 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 *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).