Hướng dẫn giải của SANGNT07: Số nguyên tố anh em
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 N (3 <= N <= 10^7), in các cặp số nguyên tố sinh đôi (a, a+2) với a+2 < N, mỗi cặp một dòng.
Sub 1: Thử chia từng số — ~O(N \sqrt{N})~, dùng khi ~N \le 1000~
Với mỗi a, kiểm tra a và a+2 có phải số nguyên tố bằng cách thử chia.
Nếu chỉ nộp sub này: đúng 17/20 test (các test N lớn bị quá giờ).
Sub 2: Sàng Eratosthenes — ~O(N \log \log N)~
Sàng các số đến N rồi in các cặp (a, a+2) đều là số nguyên tố. Bẫy: cận là a+2 < N (strict), theo đề "nhỏ hơn N".
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Main đọc N. Nếu N <= 1000 gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long N;
bool isPrimeTrial(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;
}
// Sub 1: thu chia tung cap (a, a+2) voi a+2 < N — dung khi N <= 1000
void sub1() {
for (long long a = 2; a + 2 < N; a++)
if (isPrimeTrial(a) && isPrimeTrial(a + 2))
cout << a << " " << a + 2 << "\n";
}
// Sub 2: sang Eratosthenes den N roi in cac cap (a, a+2)
void sub2() {
vector<bool> comp(N + 1, false);
comp[0] = true;
comp[1] = true;
for (long long i = 2; i * i <= N; i++)
if (!comp[i])
for (long long j = i * i; j <= N; j += i) comp[j] = true;
for (long long a = 2; a + 2 < N; a++)
if (!comp[a] && !comp[a + 2])
cout << a << " " << a + 2 << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
if (N <= 1000) sub1();
else sub2();
return 0;
}
Bình luận