Hướng dẫn giải của Đếm số nguyên tố
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cho dãy ~A_1, \dots, A_n~ và ~Q~ truy vấn ~[L, R]~, cần đếm số phần tử nguyên tố trong đoạn. Lưu ý số âm, số 0 và số 1 không phải số nguyên tố.
Sub 1: Vét cạn — ~O(n \cdot \sqrt{M} + Q \cdot n)~, dùng khi ~n \le 1000~
Kiểm tra nguyên tố từng ~A_i~ bằng thử chia (một lần cho mỗi phần tử), rồi mỗi truy vấn đếm trực tiếp trên đoạn ~[L, R]~. Nếu chỉ nộp sub này: đúng 14/20 test (các test lớn bị quá giờ).
Sub 2: Tiền tố — ~O(M \log \log M + n + Q)~, dùng cho ~n \le 10^5~
Sàng số nguyên tố đến ~10^6~ (vì ~|A_i| \le 10^6~), đếm tiền tố ~pre[i]~ = số nguyên tố trong ~A_1..A_i~. Mỗi truy vấn là ~pre[R] - pre[L-1]~ trong ~O(1)~. Chạy riêng sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Chương trình đọc ~n, Q~ và các truy vấn; nếu ~n \le 1000~ gọi sub1, còn lại gọi sub2.
Số test: 20 (chương trình đầy đủ đúng 20/20).
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 1000000; // |A_i| <= 10^6
int n, q;
long long a[100005];
int qL[100005], qR[100005];
// Kiem tra v co phai so nguyen to khong (thu chia den sqrt(v)); so am va 0, 1 khong phai nguyen to
bool isPrimeTD(long long v) {
if (v < 2) return false;
for (long long d = 2; d * d <= v; d++)
if (v % d == 0) return false;
return true;
}
// Sub 1: vet can. Kiem tra nguyen to tung A_i bang thu chia (chi 1 lan cho moi phan tu),
// moi truy van duyet truc tiep doan [L, R]. Dung khi n <= 1000
bool pr[100005];
void sub1() {
for (int i = 1; i <= n; i++) pr[i] = isPrimeTD(a[i]);
for (int k = 0; k < q; k++) {
int cnt = 0;
for (int i = qL[k]; i <= qR[k]; i++) cnt += pr[i];
cout << cnt << "\n";
}
}
// Sub 2: day du. Sang so nguyen to den 10^6, roi cong don mang tien to pre[i] = so nguyen to trong A_1..A_i.
// Moi truy van tra loi trong O(1): pre[R] - pre[L-1].
bool composite[MAXV + 1];
int pre[100005];
void sub2() {
composite[0] = composite[1] = true;
for (int i = 2; (long long)i * i <= MAXV; i++)
if (!composite[i])
for (int j = i * i; j <= MAXV; j += i) composite[j] = true;
pre[0] = 0;
for (int i = 1; i <= n; i++) {
bool p = a[i] >= 2 && !composite[a[i]];
pre[i] = pre[i - 1] + (p ? 1 : 0);
}
for (int k = 0; k < q; k++) cout << pre[qR[k]] - pre[qL[k] - 1] << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int k = 0; k < q; k++) cin >> qL[k] >> qR[k];
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận