Số Bán Nguyên Tố

Buổi 57 — Sàng & Euler Totient
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Submissions
Đề bài

Một số nguyên dương được gọi là số bán nguyên tố nếu nó là tích của đúng hai số nguyên tố (có thể giống nhau, ví dụ $4 = 2 \times 2$, $6 = 2 \times 3$). Cho $Q$ truy vấn, mỗi truy vấn cho đoạn $[L, R]$, hãy đếm số lượng số bán nguyên tố trong $[L, R]$.

Dữ liệu vào
  • Dòng đầu chứa số $Q$ ($1 \le Q \le 10^5$).
  • $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $L, R$ ($1 \le L \le R \le 10^6$).
Dữ liệu ra

Với mỗi truy vấn, in ra số lượng số bán nguyên tố trong $[L, R]$.

Ví dụ
Input Output
2
1 10
10 20
4
3
Giới hạn
  • $1 \le Q \le 10^5$
  • $1 \le L \le R \le 10^6$
Draft saved