The problem of the complexity of the exact counting problem for primes is interesting. The best result we have about primes is that it is hard for TC0. But counting the number of witnesses to a TC0 function can be as difficult as sharpP. The best upper-bound is P by AKS which gives a sharpP upper-bound for the exact counting problem.

There is no known algorithm for exact counting better that P, otherwise we would be able to check if a number x is a prime by counting the number of primes before x-1 and x and comparing them.

The problem can't be in P unless we can solve the problem of finding prime numbers in P which is an open problem: we can use a binary search to find the first prime number after x by finding the first number y>x where there are more primes before y than x.

Can we do better if we relax the question to approximate counting? I know that the question is not completely well-defined. We need to first clarify what we mean by "approximate", e.g., an absolute error or a relative error? etc. But I don't know what would be a good definition.

Given $n$, how well can we approximate the number of prime numbers below $n$ in polynomial time?

`[closed]`

at the end of your own question? I'm guessing you thought people wouldn't look at it then, and it'd stay open? (See tea.mathoverflow.net/discussion/1543) $\endgroup$1more comment