Hướng dẫn giải của [200 đề thầy Đức] Bài 95: Phân tích thừa số nguyên tố
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
Phân tích số tự nhiên $N$ thành tích các thừa số nguyên tố. Với mỗi thừa số nguyên tố $p$ có số mũ $e$, in ra cặp "p e" theo thứ tự $p$ tăng dần, các cặp cách nhau bởi dấu cách và nằm trên cùng một dòng. Ví dụ $N = 100$ cho "2 2 5 2".
Sub 1: Vét cạn — ~O(N^2)~, dùng khi ~N \le 1000~
Thử mọi số $p$ từ $2$ đến $N$. Với $p$ là số nguyên tố (kiểm tra bằng cách thử chia), nếu $p$ chia hết $N$ thì chia $N$ cho $p$ liên tục và đếm số mũ.
Kết quả chạy riêng sub này: đúng 13/21 test (8 test còn lại có $N$ lớn hơn miền của sub này).
Sub 2: Thử chia đến căn bậc hai — ~O(\sqrt{N})~
Thử $p$ từ $2$ đến $\sqrt{N}$. Mỗi lần $p$ chia hết $N$ thì $p$ là số nguyên tố, vì các ước nhỏ hơn đã bị loại hết. Chia $N$ cho $p$ liên tục để tìm số mũ. Sau khi xong, nếu $N > 1$ thì $N$ còn lại là một thừa số nguyên tố có số mũ $1$.
Bẫy cần chú ý: không được quên thừa số nguyên tố lớn còn lại sau vòng lặp, ví dụ $N = 35 = 5 \cdot 7$ thì sau khi thử $p = 2, 3, 4, 5$ còn lại $7$.
Chương trình hoàn chỉnh
Chương trình đọc $T$ bộ dữ liệu. Với mỗi $N$, nếu $N \le 1000$ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int T;
long long N;
// Sub 1: vét cạn — thử mọi số d từ 2 đến N, mỗi d nguyên tố thì chia N cho d đến hết.
// Dùng khi N <= 1000
void sub1() {
for (long long p = 2; p <= N; p++) {
bool prime = true;
for (long long q = 2; q < p; q++)
if (p % q == 0) { prime = false; break; }
if (!prime || N % p != 0) continue;
int e = 0;
while (N % p == 0) { N /= p; e++; }
cout << p << " " << e << " ";
}
cout << "\n";
}
// Sub 2: thử chia các số d từ 2 đến căn của N. Mỗi lần tìm được ước d thì d là số nguyên tố
// (vì các ước nhỏ hơn đã bị loại hết). Phần N còn lại > 1 là một thừa số nguyên tố.
void sub2() {
for (long long p = 2; p * p <= N; p++) {
if (N % p != 0) continue;
int e = 0;
while (N % p == 0) { N /= p; e++; }
cout << p << " " << e << " ";
}
if (N > 1) cout << N << " " << 1 << " ";
cout << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> T;
while (T--) {
cin >> N;
if (N <= 1000) sub1(); // N nhỏ: vét cạn
else sub2(); // N lớn: thử chia đến căn bậc hai
}
return 0;
}
Bình luận