Postulado de Bertrand
El postulado de Bertrand es un teorema que establece que, para cualquier entero
n > 1, siempre existe al menos un número primo p que se encuentra entre n y 2n .Se te solicita resolver una tarea más desafiante. Dado un número
n, debes responder preguntas como cuántos números primos p existen tales que n < p < 2n.Entrada
La primera línea de la entrada contiene un entero
t (1 ≤ t ≤ 100), que representa el número de casos de prueba.Las siguientes
t líneas contienen un entero n (2 ≤ n ≤ 500 000).Salida
El programa debe imprimir la cantidad de números primos entre
n y 2n para cada caso de prueba, cada uno en una línea independiente.Ejemplos
Entrada | Salida |
2
2
239 | 1
39 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB