Đếm số lượng nguyên tố
Xem dạng PDF
Mã bài:
countpri
Điểm:
1,2 (OI)
Giới hạn thời gian:
5.0s
C++ 20
1.0s
Giới hạn bộ nhớ:
512M
Dữ liệu vào:
stdin
Dữ liệu ra:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Golang, Java, Pascal, Perl, Python, Rust
Cho ~M~ truy vấn, mỗi truy vấn gồm ~2~ giá trị ~l_i, r_i (1 ≤ l_i ≤ r_i ≤ 10^6)~.
Với mỗi truy vấn bạn phải trả lời câu hỏi: có bao nhiêu số nguyên tố thuộc đoạn ~[l_i,r_i]~.
Dữ liệu vào
• Dòng ~1~ chứa ~M (1 ≤ M ≤ 10^6)~
• ~M~ dòng tiếp theo, mỗi dòng chứa hai số ~l_i~ và ~r_i~.
Dữ liệu ra
• Mỗi dòng chứa ~1~ câu trả lời tương ứng với truy vấn trong input.
Sample Input
3
4 10
7 20
2 30
Sample Output
2
5
10
Bình luận
ong bt cai j
prefixsum voi sang era