Hướng dẫn giải của Số nguyên tố (đề Đà Nẵng 2021)
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
Tìm b nhỏ nhất ≥ 1 sao cho a + b là số nguyên tố. Chỉ cần thử lần lượt b = 1, 2, ... và kiểm tra tính nguyên tố của a + b. Khoảng cách giữa các số nguyên tố quanh 10^9 rất nhỏ nên số lần thử ít.
Sub 1: Vét cạn kiểm tra nguyên tố — ~O(b·a)~
Thử b = 1, 2, ... và kiểm tra a + b có ước nào trong khoảng 2 đến a+b-1 không. Đúng nhưng chậm với a lớn. Đạt 9/10 test (1 test TLE, không sai).
#include <bits/stdc++.h>
using namespace std;
// Kiểm tra nguyên tố bằng cách thử mọi ước d từ 2 đến x-1 (vét cạn, chậm)
bool isPrimeSlow(long long x) {
if (x < 2) return false;
for (long long d = 2; d < x; d++)
if (x % d == 0) return false;
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long a;
cin >> a;
// Thử b = 1, 2, 3, ... cho đến khi a + b là số nguyên tố
for (long long b = 1;; b++) {
if (isPrimeSlow(a + b)) {
cout << b << "\n";
break;
}
}
return 0;
}
Sub 2: Thử ước đến căn bậc hai — ~O(b·√a)~
Khi kiểm tra x nguyên tố chỉ cần thử các ước d với d·d ≤ x, vì nếu x có ước lớn hơn căn thì cũng có ước nhỏ hơn căn. Đạt 10/10 test.
#include <bits/stdc++.h>
using namespace std;
// Kiểm tra nguyên tố: chỉ cần thử ước đến căn bậc hai của x
bool isPrime(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 a;
cin >> a;
// Khoảng cách giữa hai số nguyên tố liên tiếp quanh 10^9 rất nhỏ (< 300),
// nên vòng lặp b kết thúc nhanh
for (long long b = 1;; b++) {
if (isPrime(a + b)) {
cout << b << "\n";
break;
}
}
return 0;
}
Bình luận