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

Using combinatorial methods (due to Legendre, Lehmer, Meissel, Lagarias, Miller, Odlyzko, Deléglise, Rivat, and probably others) it's possible to count the number of primes up to $N$ quickly -- in time $O(N^{2/3})$ or even $O(N^{3/5})$. But suppose we wanted to count only the primes $p$ such that $p\equiv x\pmod m$. Is there a way to calculate this quickly, in time comparable to the above?

Of course if $m$ were large it would be faster to count the primes directly, so you can assume that $m$ is small compared to $N$.

Different methods (e.g. analytic) would also be of interest to me, but my understanding is that these are barely practical even at the largest numbers to which $\pi(N)$ has been computed and are therefore not directly of interest to me.

share|cite|improve this question

I just found Counting primes in residue classes which seems to answer my question.

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.