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$$.

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