Hướng dẫn giải của Tìm ước nguyên tố lớn nhấ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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Cho một số tự nhiên n > 1, cần tìm ước số nguyên tố lớn nhất của n. Với n < 10^12 và T < 10, ta cần một thuật toán đủ nhanh để phân tích n thành các thừa số nguyên tố.
Các cách tiếp cận
Cách Phân tích thừa số nguyên tố cơ bản
#include <bits/stdc++.h>
using namespace std;
long long l,r,R,L,cnt=0;
int main()
{
long long t;
cin >> t;
while(t--){
long long x,s=LLONG_MIN,y=0;
cin >> x;
for(long long i=2;i<=sqrt(x);i++){
while(x%i==0){
y=i;
x/=i;
}
}
if(x>1){
y=x;
}
if(y>s){
s=y;
}
cout << s << endl;
}
return 0;
}
- Time Complexity: O(√n)
- Space Complexity: O(1)
Thuật toán duyệt từ 2 đến căn bậc hai của n. Với mỗi số i, nếu chia hết thì chia n cho i cho đến khi không còn chia hết, gán y = i (ước nguyên tố). Cuối cùng, nếu n còn lại > 1 thì n đó là ước nguyên tố lớn nhất. Do chỉ duyệt đến √n, độ phức tạp là O(√n).
Cách Tối ưu với phân loại số chẵn lẻ
#include <bits/stdc++.h>
using namespace std;
long long maxPrimeFactor(long long n) {
long long maxP = -1;
while (n % 2 == 0) {
maxP = 2;
n /= 2;
}
for (long long i = 3; i * i <= n; i += 2) {
while (n % i == 0) {
maxP = i;
n /= i;
}
}
if (n > 1) maxP = n;
return maxP;
}
int main() {
int T;
cin >> T;
while (T--) {
long long n;
cin >> n;
cout << maxPrimeFactor(n) << "\n";
}
}
- Time Complexity: O(√n)
- Space Complexity: O(1)
Xử lý riêng trường hợp n chia hết cho 2 (ước nguyên tố 2). Sau đó chỉ duyệt các số lẻ từ 3, tăng bước nhảy 2 (3,5,7,...). Điều này giảm một nửa số lần lặp so với cách đầu tiên.
Cách Dùng vector lưu trữ thừa số
#include<bits/stdc++.h>
#define int long long
#define speed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define freopen freopen(".inp","r",stdin);freopen(".out","w",stdout);
using namespace std;
void div(int n){
vector<int>v;
for(int i=2;i*i<=n;i++){
int t=0;
while(n%i==0){
n/=i;
t++;
}
if(t!=0)v.push_back(i);
}
if(n>1)v.push_back(n);
int m=-1e18;
sort(v.begin(),v.end(),greater<int>());
cout<<v[0]<<endl;
}
signed main(){
speed;
int t;cin>>t;
while(t--){
int n;cin>>n;
div(n);
}
return 0;
}
- Time Complexity: O(√n log √n)
- Space Complexity: O(√n)
Phân tích n và lưu các thừa số nguyên tố vào vector, sau đó sắp xếp giảm dần và lấy phần tử đầu tiên. Cách này đúng nhưng thừa thãi vì không cần lưu trữ hay sắp xếp, chỉ cần track max ngay trong quá trình phân tích.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(√n) | O(1) | Phân tích thừa số nguyên tố cơ bản |
| 2 | O(√n) | O(1) | Tối ưu với phân loại số chẵn lẻ |
| 3 | O(√n log √n) | O(√n) | Dùng vector lưu trữ thừa số |
Bài học kinh nghiệm
- Ước nguyên tố lớn nhất của n chính là phần còn lại sau khi chia hết cho các thừa số nhỏ hơn, hoặc ước nguyên tố lớn nhất trong các thừa số đã tìm được.
- Chỉ cần duyệt đến căn bậc hai của n (√n), nếu n > 1 sau vòng lặp thì n chính là ước nguyên tố lớn nhất.
Lỗi thường gặp
- Sử dụng biến lưu ước lớn nhất nhưng không cập nhật đúng cách khi n chia hết cho nhiều thừa số giống nhau.
- Quên kiểm tra điều kiện n > 1 sau vòng lặp để lấy ước nguyên tố cuối cùng.
Bình luận