Hướng dẫn giải của SANGNT04: Đếm 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 hai số nguyên dương a, b (a <= b <= 10^7), đếm số nguyên tố trong đoạn [a, b].
Sub 1: Thử chia từng số — ~O((b-a) \sqrt{b})~, dùng khi ~b \le 5000~
Với mỗi số trong [a, b], thử chia đến căn bậc hai để kiểm tra nguyên tố.
Nếu chỉ nộp sub này: đúng 16/20 test (các test có b lớn bị quá giờ).
Sub 2: Sàng Eratosthenes — ~O(b \log \log b)~
Sàng các số đến b, rồi đếm các số nguyên tố p >= a. Bẫy: phải sàng đến b chứ không chỉ đến a.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Main đọc a, b. Nếu b <= 5000 gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long a, b;
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: thu chia tung so trong [a, b], O((b-a) * sqrt(b)) — dung khi b <= 5000
void sub1() {
long long cnt = 0;
for (long long i = a; i <= b; i++)
if (isPrimeTrial(i)) cnt++;
cout << cnt << "\n";
}
// Sub 2: sang Eratosthenes den b, roi dem so nguyen to trong [a, b]
void sub2() {
vector<bool> comp(b + 1, false);
long long cnt = 0;
for (long long i = 2; i <= b; i++) {
if (comp[i]) continue;
if (i >= a) cnt++;
for (long long j = i * i; j <= b; j += i) comp[j] = true;
}
cout << cnt << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> a >> b;
if (b <= 5000) sub1();
else sub2();
return 0;
}
Bình luận