Vi en esta publicación en stackoverflow que hay algunos algoritmos relativamente rápidos para tamizar un intervalo de números para ver si hay un primo en ese intervalo. Sin embargo, ¿esto significa que el problema de decisión general de: (¿Existe una prima en un intervalo?) Está en P. (Hubo muchas respuestas a esa publicación que no leí, así que me disculpo si esta pregunta es un duplicado o innecesario).
Por un lado, si el intervalo es lo suficientemente grande (por ejemplo ), entonces se aplica algo como el Postulado de Bertrand y definitivamente hay un primo en este intervalo. Sin embargo, también sé que hay arbitrariamente grandes brechas entre dos números primos (por ejemplo .
Incluso si el problema de decisión está en PI, no veo cómo el problema de búsqueda correspondiente también es manejable porque, entonces, es posible que no podamos recurrir a las mismas propiedades con respecto a la distribución conocida de primos al realizar una búsqueda binaria.