Suppose I give you $(a, b, M)$ and ask you to compute the number of primes not exceeding $M$ which are congruent to $b$ mod $a.$ What is the most efficient way of doing it? (without congruence restrictions there is the Meissel-Lehmer algorithm).
$\begingroup$
$\endgroup$
2
asked Feb 7, 2018 at 20:52
-
1$\begingroup$ Are you thinking of $a$ fixed, and $M$ large? Computing via the explicit formula and finding zeros of $L$-functions, would seem a good way to me -- would have complexity about $a M^{1/2+\epsilon}$. $\endgroup$– LuciaCommented Feb 7, 2018 at 21:05
-
$\begingroup$ @Lucia Yes, I am thinking of fixed $a.$ How much precision would be needed for the zeros? And without congruence conditions, is the explicit formula faster (theoretically or practically)than Meissel-Lehmer? $\endgroup$– Igor RivinCommented Feb 7, 2018 at 21:08
Add a comment
|