On the complexity of computing prime tables on a Turing machine

Abstract

We prove that the complexity of computing the table of primes between $1$ and $n$ on a multitape Turing machine is $O(n\log n)$.

6 pages