Đếm Mã Nguyên Tố Cấp Phép Chiếu Rạp

Mô tả

Cục Điện ảnh quyết định số hóa kho hồ sơ của các bộ phim từng chiếu rạp trên toàn quốc. Mỗi hồ sơ được gắn một mã số nguyên dương duy nhất từ 1 đến N. Để tối ưu quy trình rà soát lưu trữ, bộ phận kiểm duyệt muốn ưu tiên xử lý những hồ sơ mang mã nguyên tố — vì theo thống kê nội bộ, các bộ phim mang mã nguyên tố thường là tác phẩm kinh điển cần được bảo quản cẩn thận hơn.

Hệ thống lưu trữ chia hồ sơ thành nhiều khu vực, mỗi khu vực tương ứng với một khoảng mã liên tục từ L đến R (gồm cả L và R). Bạn được giao viết chương trình đọc danh sách các khu vực cần rà soát và trả lời: mỗi khu vực có bao nhiêu hồ sơ mang mã nguyên tố?

Đầu vào

• Dòng đầu tiên chứa hai số nguyên N và Q $(2 \le N \le 10^6, 1 \le Q \le 10^5)$, trong đó N là mã hồ sơ lớn nhất trong toàn hệ thống, Q là số khu vực cần rà soát.
• Q dòng tiếp theo, mỗi dòng chứa hai số nguyên L và R $(1 \le L \le R \le N)$, mô tả một khu vực cần kiểm tra.

Đầu ra

• In ra Q dòng, mỗi dòng là một số nguyên — số lượng mã nguyên tố trong khoảng [L, R] tương ứng.

Ràng buộc

• $2 \le N \le 10^6$
• $1 \le Q \le 10^5$

Ví dụ

Đầu vào:

20 3 1 10 5 15 10 20

Đầu ra:

4 4 4

Giải thích:

• Các số nguyên tố từ 1 đến 20 là: 2, 3, 5, 7, 11, 13, 17, 19.
• Khu vực [1, 10]: có 4 số nguyên tố là 2, 3, 5, 7.
• Khu vực [5, 15]: có 4 số nguyên tố là 5, 7, 11, 13.
• Khu vực [10, 20]: có 4 số nguyên tố là 11, 13, 17, 19.