Il postulato di Bertrand
Il postulato di Bertrand è un teorema che afferma che, per ogni intero
n > 1, esiste sempre almeno un numero primo p compreso tra n e 2n .Ti viene richiesto di risolvere un compito più impegnativo. Dato un numero
n, devi rispondere a domande come quante volte compare un numero primo p tale che n < p < 2n.Input
La prima riga dell’input contiene un unico intero
t (1 ≤ t ≤ 100), che indica il numero di test case.Le successive
t righe contengono un singolo intero n (2 ≤ n ≤ 500 000).Output
Il programma deve stampare il numero di numeri primi compresi tra
n e 2n per ogni test case, ciascuno su una nuova riga.Esempi
Ingresso | Uscita |
2
2
239 | 1
39 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB