Đếm nguyên tố
Xem dạng PDF
Gửi bài giải
Điểm:
10,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Số nguyên tố là số nguyên dương chỉ có duy nhất hai ước là 1 và chính nó. Ví dụ: số 11 là số nguyên tố vì nó chỉ có hai ước là 1 và 11; số 15 không phải số nguyên tố vì nó có 4 ước gồm 1, 3, 5 , 15; số 1 không phải là số nguyên tố vì nó có 1 ước là 1.
Yêu cầu: Cho số nguyên ~N~ (~1 ≤ N ≤ 2.10^5~) và N đoạn số nguyên (~1 ≤ L_i ≤ R_i ≤ 10^7~). Hãy tìm số lượng số nguyên tố thuộc mỗi đoạn
Dữ liệu vào:
- Dòng đầu tiên chứa số nguyên ~N~.
- ~N~ dòng tiếp theo, dòng thứ i chứa hai số nguyên(ngăn cách nhau bởi một khoảng trắng)
Dữ liệu ra:
- Gồm ~N~ dòng, dòng thứ i ghi một số nguyên là số lượng số nguyên tố thuộc đoạn .
Ví dụ:
Input
2
14 16
11 25
Output
0
5
Ràng buộc:
- Có 40% số test tương ứng 40% số điểm của bài với ~1 \le N \le 10^3; 1 \le L \le R \le 10^3~
- Có 60% số test tương ứng 60% số điểm của bài với ~10^3 < N \le 2.10^5; 1 \le L \le R \le 10^7~.
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
nhuấn nhũng nhim nho, nhay nhu nhó
nhuấn nhũng nhay nhọ nhéo
khó hiểu thật tôi chịu
nhàm như nhào nhó nhai nhày nhình nhới