Bach Lieu Coder - Bài tập

SH50 - Đếm số lượng nguyên tố - COUNTPRI

Dữ liệu vào: Standard input

Dữ liệu ra: Standard output

Giới hạn thời gian: 1.0 giây

Giới hạn bộ nhớ: 128 megabyte

Đăng bởi: phanhieubl

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⁶).

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].

INPUT: COUNTPRI.INP

Dòng 1 chứa M (1 ≤ M ≤ 10⁶)
M dòng tiếp theo, mỗi dòng chứa hai số li và ri.

OUTPUT: COUNTPRI.OUT

Mỗi dòng chứa 1 câu trả lời tương ứng với truy vấn trong input.

Ví dụ

COUNTPRI.INP

COUNTPRI.OUT

3

4 10

7 20

2 30

2

5

10

Ràng buộc:

subtask1: 60% số điểm tương ứng 60% số test có 1 ≤ m ≤ 10³ và 1 ≤ l_i ≤ r_i ≤ 10³
subtask2: 40% số điểm tương ứng 60% số test còn lại không có ràng buộc gì

Bài tập mới

Coder tích cực

Back to Top