Hướng dẫn giải của SANGNT09: Tổng 2 số nguyên 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 N (2 <= N <= 10^7), đếm số cách phân tích N thành tổng của hai số nguyên tố khác nhau (mỗi cách tính một lần, không tính thứ tự).
Sub 1: Thử chia từng số — ~O(N \sqrt{N})~, dùng khi ~N \le 1000~
Duyệt p với 2p < N, kiểm tra p và N-p đều nguyên tố bằng cách thử chia.
Nếu chỉ nộp sub này: đúng 18/20 test (các test N lớn bị quá giờ).
Sub 2: Sàng Eratosthenes — ~O(N \log \log N)~
Sàng đến N, rồi đếm p với 2p < N sao cho p và N-p đều nguyên tố. Bẫy: điều kiện 2p < N loại trường hợp p = N-p (ví dụ N = 3746 = 1873 + 1873), vì đề yêu cầu hai số khác nhau.
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 tung p voi 2p < N, kiem tra p va N-p deu la nguyen to bang chia thu — dung khi N <= 1000
void sub1() {
long long cnt = 0;
for (long long p = 2; 2 * p < N; p++) // 2p < N: p < N-p, hai so khac nhau
if (isPrimeTrial(p) && isPrimeTrial(N - p)) cnt++;
cout << cnt << "\n";
}
// Sub 2: sang Eratosthenes den N, roi dem p (2p < N) sao cho p va N-p deu nguyen to
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;
long long cnt = 0;
for (long long p = 2; 2 * p < N; p++) // hai so phai khac nhau
if (!comp[p] && !comp[N - p]) cnt++;
cout << cnt << "\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