Đếm số nguyên tố trong đoạn
Đề bài
Mô tả
Cho truy vấn, mỗi truy vấn gồm hai số nguyên và . Với mỗi truy vấn, hãy đếm xem có bao nhiêu số nguyên tố trong đoạn (tính cả hai đầu mút).
Một số nguyên được gọi là số nguyên tố nếu nó chỉ chia hết cho và chính nó. Lưu ý rằng không phải là số nguyên tố.
Dữ liệu vào
- Dòng đầu chứa số nguyên — số truy vấn.
- dòng tiếp theo, mỗi dòng chứa hai số nguyên và .
Dữ liệu ra
Với mỗi truy vấn, in ra một dòng chứa số lượng số nguyên tố trong đoạn .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 1 10 2 2 1 1 |
4 1 0 |
Truy vấn 1: các số nguyên tố trong [1,10] là 2, 3, 5, 7 — có 4 số. Truy vấn 2: chỉ có 2 là nguyên tố. Truy vấn 3: 1 không phải nguyên tố, kết quả là 0. |
| 2 10 20 14 16 |
4 0 |
Truy vấn 1: các số nguyên tố trong [10,20] là 11, 13, 17, 19. Truy vấn 2: trong [14,16] không có số nguyên tố nào. |
Ghi chú
Có thể có nhiều truy vấn có cùng giá trị .
Bình luận