# The computational complexity of prime sieving

Given a subset \([1,n] \subset \mathbb{N}\) and prime \(p \leq n\) the number of integers in \([1,n]\) divisible by \(p\) is \(\lfloor \frac{n}{p} \rfloor\) so the number of division operations is also \(\lfloor \frac{n}{p} \rfloor\).

It follows that in order to find all prime numbers less than or equal to \(n\), the number of division operations is on the order of:

\begin{equation} n \sum_{p \leq n} \frac{1}{p} \end{equation}

and by Mertens’ second theorem:

\begin{equation} \sum_{p \leq n} \frac{1}{p} = \ln \ln n + \mathcal{O}(1) \end{equation}

so the number of FLOPs for a prime sieve that filters all primes less than \(n\) is on the order of \(\sim n \cdot \ln \ln n\).

In principle, this makes the Sieve of Eratosthenes polynomial in time complexity. However, given that the description length of \(n \in \mathbb{N}\) is on the order of \(\sim \log_2 n\) the time complexity is actually exponential in the input size. In fact, if \(N := \log_2 n\) then the time complexity of sieving all primes less than \(n\) is on the order of:

\begin{equation} \sim 2^N \ln N \end{equation}

This is not the last word on the subject however since on average the computational cost of sieving an integer in \([1,n]\) is on the order of:

\begin{equation} \frac{2^N \ln N}{2^N} \sim \ln N \end{equation}

whereas the time complexity for factoring a single integer sampled uniformly in \([n+1,2n]\) is exponential in \(N\).

## References:

- Havil, J. Gamma: Exploring Euler’s Constant. Princeton, NJ: Princeton University Press, p. 109, 2003.
- Weisstein, Eric W. “Mertens’ Second Theorem.” From MathWorld–A Wolfram Web Resource. https://mathworld.wolfram.com/MertensSecondTheorem.html