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.
