O postulado de Bertrand
O postulado de Bertrand é um teorema que estabelece que, para qualquer inteiro
n > 1, existe sempre pelo menos um número primo p que se encontra entre n e 2n (isto é, n < p < 2n).É pedido que resolva uma tarefa mais desafiadora. Dado um número
n, deve determinar quantos números primos p existem tais que n < p < 2n.Entrada
A primeira linha da entrada contém um inteiro
t (1 ≤ t ≤ 100), que representa o número de casos de teste.As seguintes
t linhas contêm cada uma um inteiro n (2 ≤ n ≤ 500 000).Saída
Para cada caso de teste, o programa deve imprimir, numa linha separada, quantos números primos existem entre
n e 2n.Exemplos
Entrada | Saída |
2
2
239 | 1
39 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB