MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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.

share|cite|improve this answer

I think is pretty up-to-date.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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