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?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
3
$\begingroup$

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

Improve this answer
$\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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .