Hướng dẫn giải của SANGNT10: Đếm số nguyên tố trong đoạn
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
Có K đoạn [A, B] (K <= 10^3, B <= 10^7), với mỗi đoạn in số lượng số nguyên tố trong đoạn đó. Đề dùng file SANGNT10.INP và SANGNT10.OUT.
Sub 1: Thử chia từng số trong từng đoạn — ~O(K \cdot (B-A) \sqrt{B})~, dùng khi ~B \le 1000~
Với mỗi đoạn, duyệt từng số và thử chia để kiểm tra nguyên tố.
Nếu chỉ nộp sub này: đúng 10/20 test (các test B lớn bị quá giờ).
Sub 2: Sàng và tổng tiền tố — ~O(B_{max} \log \log B_{max} + K)~
Sàng một lần đến max(B), lập mảng pre[x] = số nguyên tố <= x. Khi đó số nguyên tố trong [A, B] là pre[B] - pre[A-1], trả lời mỗi đoạn O(1). Bẫy: phải lấy A-1 khi A=1 (pre[0]=0).
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Main đọc file SANGNT10.INP, đọc K đoạn. Nếu max(B) <= 1000 gọi sub1, ngược lại gọi sub2. Kết quả ghi ra SANGNT10.OUT qua freopen.
#include <bits/stdc++.h>
using namespace std;
int K;
vector<long long> A, B; // A[i], B[i]: doan thu i
bool isPrimeTrial(long long x) {
if (x < 2) return false;
for (long long d = 2; d * d <= x; d++)
if (x % d == 0) return false;
return true;
}
// Sub 1: voi moi doan, thu chia tung so trong [A, B] — dung khi moi B <= 1000
void sub1() {
for (int i = 0; i < K; i++) {
long long cnt = 0;
for (long long x = A[i]; x <= B[i]; x++)
if (isPrimeTrial(x)) cnt++;
cout << cnt << "\n";
}
}
// Sub 2: sang Eratosthenes den max(B) mot lan, dung tong tien to de tra loi moi doan O(1)
void sub2() {
long long mx = 2;
for (int i = 0; i < K; i++) mx = max(mx, B[i]);
vector<bool> comp(mx + 1, false);
comp[0] = true;
comp[1] = true;
for (long long i = 2; i * i <= mx; i++)
if (!comp[i])
for (long long j = i * i; j <= mx; j += i) comp[j] = true;
// pre[x] = so nguyen to <= x
vector<int> pre(mx + 1, 0);
for (long long x = 1; x <= mx; x++) pre[x] = pre[x - 1] + (comp[x] ? 0 : 1);
for (int i = 0; i < K; i++)
cout << pre[B[i]] - pre[A[i] - 1] << "\n";
}
int main() {
freopen("SANGNT10.INP", "r", stdin);
freopen("SANGNT10.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> K;
A.resize(K);
B.resize(K);
for (int i = 0; i < K; i++) cin >> A[i] >> B[i];
if (*max_element(B.begin(), B.end()) <= 1000) sub1();
else sub2();
return 0;
}
Bình luận