Hướng dẫn giải của SANGNT02: Kiểm tra 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 N số nguyên dương Ai, cần in ra 1 nếu Ai là số nguyên tố, 0 nếu không. Có 20% số điểm với N <= 10^3, còn lại N <= 10^6 và A_i <= 10^7.
Sub 1: Thử chia trực tiếp — ~O(n \cdot \sqrt{A})~, dùng khi ~n \le 1000~
Với mỗi số, thử chia cho các số d từ 2 đến căn bậc hai của nó. Nếu có ước thì không phải số nguyên tố. Cách này đơn giản nhưng với N lớn sẽ chậm.
Nếu chỉ nộp sub này: đúng 16/20 test (các test N lớn bị quá giờ).
Sub 2: Sàng Eratosthenes — ~O(A \log \log A + n)~
Sàng toàn bộ các số từ 0 đến max(Ai) một lần, đánh dấu hợp số. Sau đó mỗi số chỉ cần tra bảng O(1). Bẫy: phải sàng tới max(Ai) (tối đa 10^7), dùng long long cho chỉ số vòng lặp i * i để tránh tràn.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu. Nếu N <= 1000 thì gọi sub1 cho chắc, ngược lại gọi sub2. Khi đi thi, sub sau có sai thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a;
// Sub 1: thu chia truc tiep den can bac hai, O(n * sqrt(A)) — dung khi n <= 1000
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;
}
void sub1() {
for (int i = 0; i < n; i++)
cout << (isPrimeTrial(a[i]) ? 1 : 0) << "\n";
}
// Sub 2: sang nguyen to Eratosthenes toi max(A) roi tra loi O(1) cho moi so
void sub2() {
long long mx = 2;
for (int i = 0; i < n; i++) mx = max(mx, a[i]);
vector<bool> comp(mx + 1, false);
comp[0] = true;
if (mx >= 1) 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;
for (int i = 0; i < n; i++)
cout << (comp[a[i]] ? 0 : 1) << "\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 <= 1000) sub1(); // du lieu nho: chia thu cho chac
else sub2(); // du lieu lon: sang nguyen to
return 0;
}
Bình luận