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:

$$n \sum_{p \leq n} \frac{1}{p}$$

and by Mertens’ second theorem:

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

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:

$$\sim 2^N \ln N$$

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:

$$\frac{2^N \ln N}{2^N} \sim \ln N$$

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

## References:

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