Hướng dẫn giải của LIST20: Các 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
Đếm các số nguyên tố trong dãy ~n~ số (số âm không phải số nguyên tố) và in chúng giảm dần.
Sub 1: Thử chia từng số — ~O(n \sqrt{M} + k \log k)~, dùng khi ~n \le 10^4~
Với mỗi phần tử, kiểm tra nguyên tố bằng thử chia đến căn bậc hai, lấy các số nguyên tố rồi sắp xếp giảm dần.
Nếu chỉ nộp sub này: đúng 19/20 test.
Sub 2: Sàng số nguyên tố — ~O(M \log \log M + k \log k)~, dùng khi mọi trường hợp còn lại
Sàng số nguyên tố đến ~M = \max|A_i|~ (không quá ~10^6~), rồi kiểm tra từng phần tử trong ~O(1)~ và sắp xếp giảm dần.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Đề không chia subtask. Sub 1 kiểm tra từng số bằng thử chia, sub 2 dùng sàng.
Chương trình đọc ~n~ và dãy. Nếu ~n \le 10^4~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a;
// Kiem tra nguyen to bang thu chia (sub 1). So am va 0, 1 khong phai nguyen to.
bool laNguyenTo(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: kiem tra tung so bang thu chia. Dung khi n <= 10000
void sub1() {
vector<long long> p;
for (int i = 0; i < n; i++)
if (laNguyenTo(a[i])) p.push_back(a[i]);
sort(p.begin(), p.end(), greater<long long>());
cout << p.size() << "\n";
for (size_t i = 0; i < p.size(); i++) cout << p[i] << (i + 1 < p.size() ? ' ' : '\n');
if (p.empty()) cout << "\n";
}
// Sub 2: sang nguyen to den max|A| (A <= 10^6) roi kiem tra O(1) cho moi so
void sub2() {
long long M = 2;
for (int i = 0; i < n; i++) M = max(M, llabs(a[i]));
vector<bool> comp(M + 1, false);
comp[0] = comp[1] = true;
for (long long i = 2; i * i <= M; i++)
if (!comp[i])
for (long long j = i * i; j <= M; j += i) comp[j] = true;
vector<long long> p;
for (int i = 0; i < n; i++)
if (a[i] >= 2 && !comp[a[i]]) p.push_back(a[i]);
sort(p.begin(), p.end(), greater<long long>());
cout << p.size() << "\n";
for (size_t i = 0; i < p.size(); i++) cout << p[i] << (i + 1 < p.size() ? ' ' : '\n');
if (p.empty()) cout << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 10000) sub1();
else sub2();
return 0;
}
Bình luận