ベルトランの仮説
ベルトランの仮説は、
n > 1 をみたす任意の整数 n について、n < p < 2nを満たす素数 p が必ず少なくとも一つは存在する、という定理です。今回は、もう少し発展的な課題として、与えられた整数
n に対して、n < p < 2n を満たす素数 p が何個あるのかを答える問題を解いていただきます。入力
入力の最初の行には、テストケースの数を示す単一の整数
t (1 ≤ t ≤ 100) が与えられます。続く
t 行それぞれに、単一の整数 n (2 ≤ n ≤ 500 000) が与えられます。出力
各テストケースごとに、
n < p < 2nを満たす素数 p の個数を 1 行ずつ出力してください。例
入力 | 出力 |
2
2
239 | 1
39 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB