I saw from this post on stackoverflow that there are some relatively fast algorithms for sieving an interval of numbers to see if there is a prime in that interval. However, does this mean that the overall decision problem of: (Does there exists a prime in an interval?) is in P. (There were a lot of answers to that post that I did not read so I apologize if this question is a duplicate or unnecessary).
On the one hand, if the interval is large enough (for example $[N,2N]$) then something like Bertrand's Postulate applies and there is definitely a prime in this interval. However, I also know that there are arbitrarily large gaps between two primes (for example $[N!,N!+ N]$.
Even if the decision problem is in P I don't see how the corresponding search problem is also tractable because, then we may not be able to draw on the same properties regarding the known distribution of primes when performing binary search.