Sieving Primes 2

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.

comments powered by Disqus