Success! I found a reference to Mertens’ theorem in a paper by Adam Kalai, which is exactly what I needed to analyze the complexity of the prime sieve from the previous post.

Alas, my previous complexity guess was wrong. The actual complexity is $O(n^{3/2} / \log^3 n)$. Apparently my numerical estimates didn’t go out far enough (also I was biased towards finding $O(n \log^m n)$).

From before, the cost of the algorithm is $O(C(n))$ where
$$C(n) = \sum_{c \lt n} \pi(lpf(c ))$$
where $c \lt n$ means all composite numbers up to $n$. Note that any number
with $lpf(c )=p$ can be written as $pm$, where $m$ is not divisible by any
prime smaller than $p$. By Mertens’ theorem, the density of numbers not
divisible by primes less than $p$ is
$$
\begin{aligned}
\prod_{q \lt p} \left(1 - \frac{1}{q}\right) &\approx& \frac{e^{-\gamma}}{\log p}
\end{aligned}
$$
We can now estimate $C(n)$ as
$$
\begin{aligned}
C(n) =~& \sum_{c \lt n} \pi(lpf(c )) \\

=~& \sum_{p \lt n} \pi(p) \sum_{k = p}^{n/p} 1\,\text{if}\,\forall q \lt p, q \nmid k \\

\approx~& \sum_{p \lt \sqrt{n}} \pi(p)\left(\frac{n}{p}-p\right) \prod_{q \lt p} \left(1 - \frac{1}{q}\right) \\

\approx~& e^{-\gamma} \sum_{p \lt \sqrt{n}} \pi(p)\left(\frac{n}{p}-p\right) \frac{1}{\log p} \\

\approx~& e^{-\gamma} \int_2^{\sqrt{n}} \pi(x) \left(\frac{n}{x}-x\right) \frac{1}{\log x} \frac{dx}{\log x} \\

\approx~& e^{-\gamma} \int_2^{\sqrt{n}} \frac{x}{\log^3 x} \left(\frac{n}{x}-x\right) \\

\approx~& e^{-\gamma} \int_2^{\sqrt{n}}\, \frac{n - x^2}{\log^3 x}
\end{aligned}
$$
Since the integrand is $O(n / \log^3 n)$ for $x \gt n^{1/3}$, we get $C(n) =
O(n^{3/2} / \log^3 n)$. On the other hand, the integrand is $\omega(n / \log^3
n)$ for $x \lt \sqrt{n/4}$, so in fact $C(n) = \Theta(n^{3/2} / \log^3 n)$.

This adds another entry to the set of listful Sieve of Eratostheness-like algorithms that turn out to cost as much as trial division (up to a polylog factor). It’d be cool if a faster list based algorithm existed, but I expect that the answer is probably no.