On the complexity of computing prime tables

Martin Farach-Colton, Meng-Tsung Tsai

Many large arithmetic computations rely on tables of all primes less than $n$. For example, the fastest algorithms for computing $n!$ takes time $O(M(n\log n)+P(n))$, where $M(n)…