Chọn ĐTQG Vĩnh Long 2025 - Nguyên tố
Xem dạng PDF
Gửi bài giải
Điểm:
14,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT
Số nguyên tố là số tự nhiên lớn hơn ~1~, chỉ có đúng hai ước số dương là ~1~ và chính nó.
Cho hai số nguyên dương ~X~ và ~Y~.
Yêu cầu: Hãy đếm trong đoạn từ ~X~ đến ~Y~ có bao nhiêu số thỏa mãn: số lượng các ước của nó là số nguyên tố.
Input
Dòng thứ nhất chứa số ~T~ ~(T \le 10^5)~ là số lượng các đoạn cần đếm.
~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~X~ và ~Y~ ~(1 \le X \le Y \le 10^6)~.
Các số trên cùng dòng cách nhau ít nhất một dấu cách.
Output
Gồm ~T~ dòng, mỗi dòng gồm một số nguyên duy nhất là kết quả cần tìm.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~6/14~ test | ~T \le 10^2, 1 \le X \le Y \le 10^3~ |
| 2 | ~4/14~ test | ~T \le 10^3, 1 \le X \le Y \le 2 \cdot 10^3~ |
| 3 | ~4/14~ test | Không có ràng buộc gì thêm |
Sample Input 1
2
1 5
10 50
Sample Output 1
4
14
Notes
Xét trường hợp ~X = 1, Y = 5~:
- Số ~1~ có ~1~ ước (số ước không phải nguyên tố).
- Số ~2~ có ~2~ ước (số ước là nguyên tố).
- Số ~3~ có ~2~ ước (số ước là nguyên tố).
- Số ~4~ có ~3~ ước (số ước là nguyên tố).
- Số ~5~ có ~2~ ước (số ước là nguyên tố).
Kết quả: ~4~.
Bình luận