DHBB 2023 - CBN - 10 - Số nguyên tố
Xem dạng PDF
Gửi bài giải
Điểm:
40,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT
Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Vì biết Nhật rất kém về số nguyên tố nên trong kì thi này của trường Newton, thầy Nam đã ra một bài toán hóc búa như sau:
Cho hai số nguyên dương ~a, b~. Hãy tìm số lượng các số trong khoảng ~[a,b]~ sao cho số lượng ước của chúng là một số nguyên tố.
Không chỉ dừng lại đó, thầy Nam còn đánh đố Nhật bằng cách không chỉ cho một bộ ~a, b~ mà cho những ~T~ bộ số.
Nhật rất cần qua kì thi này nên anh ấy nhờ đến các bạn lập trình chương trình để giải bài toán của thầy Nam.
Input
Dòng đầu chứa số nguyên dương ~T~ là số bộ test;
~T~ dòng sau, mỗi dòng gồm hai số nguyên dương ~a, b~.
Output
Gồm ~T~ dòng, dòng thứ ~i~ là kết quả của bộ test thứ ~i~.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~20\%~ | ~1 \le a,b \le 200, T \le 100~ |
| 2 | ~20\%~ | ~1 \le a,b \le 2000, T \le 1000~ |
| 3 | ~20\%~ | ~1 \le a,b \le 10^6, T \le 1000~ |
| 4 | ~20\%~ | ~1 \le a,b \le 10^6, T \le 10^5~ |
| 5 | ~20\%~ | ~10^6 < a,b \le 10^{12}, T \le 10^5~; số lượng ước phải là số nguyên tố lớn hơn ~2~ |
Sample Input 1
5
12 400
412 1000
32 100
1910 3000
1 100
Sample Output 1
82
93
17
141
32
Bình luận