Skip to main content
3 of 9
added 12 characters in body

The next prime number within the same range after about $10^8$. Eratosthenes is as fast as $O(n)=n\log(\log(n))$, while the best known algorithm for Riemann zeros is far from trivial and about $O(n)=n^{1+\epsilon}$ where if you want to reduce $\epsilon$ you need more space.

The difference is that you can find a very large Riemann zero without knowing any previous zero, while you need to find quite some number of all primes before any given value, if you want to be 100% sure that you have found a prime number. For example, in the most primitive implementation of Eratosthenes sieve, if you have first $n$ primes you can find primes up to $n^2$, but you still need to list first $n$ primes.

You can, however, use some algorithms that are testing if a number is prime, but then you have to scan some region in order to find a prime number. The best known deterministic is way faster than any known Riemann zeta algorithm, it is known as AKS algorithm and has $O(\log(n)^6)$. Above that you are left with quick, but only probabilistic algorithms, for prime numbers.

Overall prime is a winner. For Riemann zeta you do have a quick estimation that are trivial to calculate alike if all zeros are in the form of $\frac{1}{2} \pm i\gamma(n)$, meaning Reimann hypothesis is correct then

$$\gamma_n \approx 2 \pi \frac{n-\frac{11}{8}}{W(\frac{n-\frac{11}{8}}{e})}$$

where W is Lambert W function.