Hướng dẫn giải của SANGNT05: Số nguyên tố lớn nhấ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, tìm số nguyên tố lớn nhất nhỏ hơn N. Vì các số nguyên tố khá dày, ta chỉ cần lùi dần từ N-1 và kiểm tra từng số.
Sub 1: Vét cạn — ~O(N^2)~
Với mỗi số a từ N-1 trở xuống, đếm mọi ước của a từ 1 đến a. Nếu đếm được đúng 2 ước thì a là số nguyên tố, in ra và dừng. Cách này đúng nhưng mỗi lần kiểm tra mất O(a).
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ố x có phải số nguyên tố bằng cách đếm mọi ước từ 1 đến x
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ử lần lượt các số từ n-1 trở xuống
for (long long a = n - 1; a >= 2; a--) {
if (laSNT(a)) {
cout << a << "\n";
break;
}
}
return 0;
}
Sub 2: Thử chia đến căn bậc hai — ~O(√N · khoảng cách)~
Kiểm tra nguyên tố bằng cách thử chia cho các số d với d·d ≤ x, chỉ cần O(√x) phép chia. Lùi từ N-1 và dừng ở số nguyên tố đầu tiên gặp được. Khoảng cách giữa hai số nguyên tố liên tiếp rất nhỏ nên số lần kiểm tra ít.
Kết quả chấm: đạt 20/20 test
#include <bits/stdc++.h>
using namespace std;
// Kiểm tra nguyên tố bằng thử chia đến căn bậc hai: O(sqrt(x))
bool laSNT(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;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
// Số nguyên tố gần nhất nhỏ hơn n: khoảng cách giữa hai số nguyên tố liên tiếp rất nhỏ
for (long long a = n - 1; a >= 2; a--) {
if (laSNT(a)) {
cout << a << "\n";
break;
}
}
return 0;
}
Bình luận