Le postulat de Bertrand
Le postulat de Bertrand est un théorème qui affirme que pour tout entier
n > 1, il existe au moins un nombre premier p compris entre n et 2n .On vous propose un défi plus avancé : étant donné un nombre
n, il s’agit de déterminer combien de nombres premiers p satisfont n < p < 2n.Entrée
La première ligne de l’entrée contient un entier
t (1 ≤ t ≤ 100), qui représente le nombre de jeux de test.Les
t lignes suivantes contiennent chacune un entier n (2 ≤ n ≤ 500 000).Sortie
Pour chaque jeu de test, le programme doit afficher le nombre de nombres premiers compris entre
n et 2n, chaque résultat sur une ligne distincte.Exemples
Entrée | Sortie |
2
2
239 | 1
39 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB