Hướng dẫn giải của SANGNT08: Các ước 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 số nguyên dương N, in ra các ước nguyên tố của N, không kể chính N. Nếu không có ước nào thì in NONE. Lưu ý: nếu N là số nguyên tố thì chỉ có ước N, nên kết quả là NONE.
Sub 1: Vét cạn — ~O(N·√N)~
Thử mọi p từ 2 đến N-1, nếu p vừa chia hết N vừa là số nguyên tố (kiểm tra bằng thử chia) thì in ra p. Cách này đúng nhưng với N lên đến 10^7 thì chậm.
Kết quả chấm: đạt 20/20 test (SUB ok 20/20, TLE 0, WA 0)
#include <bits/stdc++.h>
using namespace std;
// Kiểm tra số nguyên tố bằng cách đếm ước (chậm)
bool laSNT(long long x) {
if (x < 2) return false;
int dem = 0;
for (long long d = 1; d <= x; d++)
if (x % d == 0) dem++;
return dem == 2;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
// Vét cạn: thử mọi p từ 2 đến n-1, lấy p vừa là ước của n vừa là số nguyên tố
bool co = false;
for (long long p = 2; p < n; p++) {
if (n % p == 0 && laSNT(p)) {
cout << p << " ";
co = true;
}
}
if (!co) cout << "NONE";
cout << "\n";
return 0;
}
Sub 2: Phân tích thừa số bằng thử chia đến căn bậc hai — ~O(√N)~
Thử chia N cho các số d từ 2 với d·d ≤ N. Mỗi khi d là ước thì d chắc chắn là số nguyên tố (vì các thừa số nhỏ hơn đã bị loại bỏ hết), ta lưu d rồi chia hết d khỏi N. Phần còn lại sau cùng nếu lớn hơn 1 cũng là một ước nguyên tố. Cuối cùng bỏ qua giá trị bằng chính N.
Kết quả chấm: đạt 20/20 test
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
long long goc = n;
vector<long long> ds; // các ước nguyên tố của n, theo thứ tự tăng dần
// Phân tích thừa số bằng thử chia đến căn bậc hai
for (long long d = 2; d * d <= n; d++) {
if (n % d == 0) {
ds.push_back(d);
while (n % d == 0) n /= d;
}
}
// Phần còn lại (nếu > 1) cũng là một ước nguyên tố
if (n > 1) ds.push_back(n);
bool co = false;
for (long long p : ds) {
if (p == goc) continue; // không kể chính N
cout << p << " ";
co = true;
}
if (!co) cout << "NONE";
cout << "\n";
return 0;
}
Bình luận