Đếm số nguyên tố trong đoạn

Hướng tiếp cận

Bài toán có nhiều truy vấn đếm số nguyên tố trong các đoạn. Giá trị tối đa $R\le {10}^6$ nên ta có thể tiền xử lý một lần: dùng sàng Eratosthenes để xác định những số nào là nguyên tố, rồi xây dựng mảng tiền tố đếm số nguyên tố. Mỗi truy vấn sau đó được trả lời trong $O(1)$.

Nhận xét quan trọng

1. $1$ không phải là số nguyên tố — cần khởi tạo is_prime[0] = is_prime[1] = 0.
2. Đếm số nguyên tố trong đoạn $[L,R]$ chính là $\mathrm{c}\mathrm{n}\mathrm{t}[R]-\mathrm{c}\mathrm{n}\mathrm{t}[L-1]$, trong đó $\mathrm{c}\mathrm{n}\mathrm{t}[i]$ là số nguyên tố trong $[1,i]$. Lưu ý chỉ số $L-1$, không phải $L$.
3. Vì $L\ge 1$, biểu thức $L-1\ge 0$ luôn hợp lệ nếu mảng $\mathrm{c}\mathrm{n}\mathrm{t}$ có chỉ số $0$.

Thuật toán

1. Đặt $M={10}^6$. Khởi tạo mảng is_prime kích thước $M+1$ với giá trị $1$, đặt is_prime[0] = is_prime[1] = 0.
2. Sàng Eratosthenes: với mỗi $i$ từ $2$ đến $\sqrt{M}$, nếu is_prime[i] = 1 thì đánh dấu is_prime[j] = 0 với mọi $j=i^2,i^2+i,\dots ,M$.
3. Xây dựng mảng tiền tố cnt[0..M]: cnt[0] = 0, cnt[i] = cnt[i-1] + is_prime[i].
4. Với mỗi truy vấn $(L,R)$, in ra cnt[R] - cnt[L-1].

Trong Python, dùng bytearray cho mảng is_prime và sys.stdin.buffer để đọc nhanh.

Độ phức tạp

• Thời gian: $O(M\log \log M+q)$ trong đó $M={10}^6$.
• Bộ nhớ: $O(M)$.