I guess the question says it all – I'm trying to track down fast algorithms for prime counting to know what's out there.
I'm already familiar with the two algorithms mentioned in the title (essentially sections 3.6.1 and 3.6.2 of my 2001 copy of Crandall & Pomerance's Prime Numbers: A Computational Perspective, although from looking online, it looks like they might be section 3.7.1 and 3.7.2 of a more recent addition).
Are there any other families of algorithms in the ballpark of, say, O(n^2/3 + epsilon) time and O(n^1/2+epsilon) space or better for prime counting? And if so, where could I find them? Is there any good repository of various prime counting algorithms anywhere on the web?
Best Answer
I don't know if this might interest you, but there is a nice formula due to Lifchitz which allows to compute the parity of $\pi(x)$ in $O(\sqrt{x}\log x)$: if $\Pi(x)$ represent the number of prime powers up to $x$ then
$$ \Pi(x) \equiv \sum_{m\leq \sqrt{x}} \mu(m) \sum_{n\leq \sqrt(x/m^2)} \left\lfloor\frac{x}{nm^2}\right\rfloor \pmod{2} $$ This is more like a comment, but I can't comment as I have not enough reputation.