HIOJ

问题1482--两质整数

_{[命题人 : ]}

时间限制 : 1.000 sec 内存限制 : 128 MB

“两质整数”指能表示成两个质数乘积的整数。

质数——又称为素数，一个大于 1 的自然数，除了 1 和本身外没有其它因子。

比如：15 就是“两质整数”，因为 15 可表示成 3 和 5 两个质数的乘积。

本题有 Q 组询问，每次询问 L,R 0 < L <= R 之间共有多少个“两质整数”。

第一行，一个整数 Q.后面 Q 行每行有两个用空格隔开的整数Li,Ri ，Li <= Ri ，表示询问区间【Li,Ri 】。

中一共有多少个“两质整数。

【数据范围】

对于 30%的数据，1 ≤ Q ≤ 10³ , 1 ≤ Li ≤ Ri <= 10³ .

对于 60%的数据，1 ≤ Q ≤ 10⁵, 1 ≤ Li ≤ Ri ≤ 10⁵ .

对于 100%的数据，1 ≤ Q ≤ 10⁵ , 1 ≤ Li ≤ Ri ≤ 10⁷

Q 行，每行一个整数，表示询问的答案。

7
12
13

【样例说明】

第一个询问，[10, 30]中共有 7 个“两质整数”：

10 = 2 × 5

14 = 2 × 7

15 = 3 × 5

21 = 3 × 7

22 = 2 × 11

25 = 5 × 5

26 = 2 × 13

其余两个询问同理。

提交