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

Here’s an interesting lazy variant of the sieve of Eratosthenes by Nick Chapman, from a discussion on LTU: primes = 2 : diff [3..] (composites primes) composites (p:ps) = cs where cs = (pp) : merge (map (p) (merge ps cs)) (composites ps) merge (x:xs) (y:ys) | xy = diff (x:xs) ys In words, the algorithm computes the list of primes as all numbers which are not composites, and the computes the list of composites by extremely constructing and merging all prime factorizations.