8
$\begingroup$

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?

$\endgroup$

3 Answers 3

6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

I think http://primes.utm.edu/howmany.shtml is pretty up-to-date.

$\endgroup$
3
$\begingroup$

Here is an overview of a bunch of different algorithms for counting and enumerating primes with a bunch of links to more in depth discussion

http://www.mail-archive.com/[email protected]/msg44646.html

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.