Hướng dẫn giải của Phân tích thành tổng hai số nguyên 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 số nguyên dương n (2 ≤ n ≤ 3×10^5). Tìm tất cả các cách phân tích n thành tổng của hai số nguyên tố phân biệt u, v (với u < v). Yêu cầu in ra số lượng cách phân tích và liệt kê các cặp (u, v) theo thứ tự tăng dần của u.
Các cách tiếp cận
Cách Brute Force với sàng nguyên tố
#include <bits/stdc++.h>
using namespace std;
const int MAX = 300005;
bool isPrime[MAX];
void sieve() {
fill(isPrime, isPrime + MAX, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i < MAX; ++i) {
if (isPrime[i]) {
for (int j = i * i; j < MAX; j += i) {
isPrime[j] = false;
}
}
}
}
int main() {
int n;
cin >> n;
sieve();
vector<pair<int, int>> ans;
// Duyệt u từ 2 đến n/2
for (int u = 2; u <= n / 2; ++u) {
int v = n - u;
if (isPrime[u] && isPrime[v] && u < v) {
ans.push_back({u, v});
}
}
cout << ans.size() << "\n";
for (auto p : ans) {
cout << p.first << " " << p.second << "\n";
}
return 0;
}
- Time Complexity: O(n log log n + n/2) ≈ O(n)
- Space Complexity: O(n)
Approach này sử dụng sàng Eratosthenes để tạo mảng đánh dấu số nguyên tố. Sau đó, duyệt qua tất cả các số u từ 2 đến n/2, kiểm tra xem u và n-u có phải là số nguyên tố phân biệt không. Đây là cách tiếp cận trực quan nhất và dễ hiểu.
Cách Optimized với sàng và kiểm tra nhanh
#include <bits/stdc++.h>
using namespace std;
const int MAX = 300005;
bool isPrime[MAX];
vector<pair<int, int>> solutions;
void sieveAndFind(int n) {
fill(isPrime, isPrime + MAX, true);
isPrime[0] = isPrime[1] = false;
// Sàng Eratosthenes
for (int i = 2; i * i < MAX; ++i) {
if (isPrime[i]) {
for (int j = i * i; j < MAX; j += i) {
isPrime[j] = false;
}
}
}
// Tìm các cặp phân tích
for (int u = 2; u <= n / 2; ++u) {
if (isPrime[u] && isPrime[n - u] && u != n - u) {
solutions.push_back({u, n - u});
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
sieveAndFind(n);
cout << solutions.size() << "\n";
for (auto p : solutions) {
cout << p.first << " " << p.second << "\n";
}
return 0;
}
- Time Complexity: O(n log log n + n/2) ≈ O(n)
- Space Complexity: O(n)
Đây là phiên bản tối ưu hơn của approach 1. Sử dụng iosbase::syncwith_stdio(0) và cin.tie(0) để tăng tốc độ nhập xuất. Code được cấu trúc hóa rõ ràng hơn với hàm sieveAndFind riêng biệt. Logic cơ bản vẫn là duyệt từ 2 đến n/2 và kiểm tra.
Cách Tối ưu với sàng trước (Precomputation)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 300005;
const int SIEVE_LIMIT = 1000000;
bool isPrime[SIEVE_LIMIT];
void precomputePrimes() {
fill(isPrime, isPrime + SIEVE_LIMIT, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i < SIEVE_LIMIT; ++i) {
if (isPrime[i]) {
for (int j = i * i; j < SIEVE_LIMIT; j += i) {
isPrime[j] = false;
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
precomputePrimes();
int n;
while (cin >> n) {
vector<pair<int, int>> ans;
for (int u = 2; u <= n / 2; ++u) {
if (isPrime[u] && isPrime[n - u] && u != n - u) {
ans.push_back({u, n - u});
}
}
cout << ans.size() << "\n";
for (auto p : ans) {
cout << p.first << " " << p.second << "\n";
}
}
return 0;
}
- Time Complexity: O(SIEVELIMIT log log SIEVELIMIT + n/2)
- Space Complexity: O(SIEVE_LIMIT)
Approach này sàng số nguyên tố lên đến một giới hạn đủ lớn (1 triệu) trước, sau đó với mỗi test case, chỉ cần kiểm tra O(n/2) lần. Trong trường hợp chỉ có một test case, hiệu năng tương đương, nhưng nếu có nhiều test case thì cách này hiệu quả hơn.
Cách Phiên bản giống solutions của contest
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll nmax = 3000005;
ll n, a[nmax], c[nmax], k = 0, dem = 0;
void nt(ll n) {
for(ll i = 0; i <= n; i++) a[i] = 1;
a[0] = a[1] = 0;
for(ll i = 2; i <= sqrt(n); i++){
if(a[i] == 1){
for(ll j = i * i; j <= n; j += i){
a[j] = 0;
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
ll m = n;
// Sàng đến 1 triệu
nt(1000000);
for(ll i = 2; i <= n / 2; i++){
if(a[i] == 1 && a[m - i] == 1 && i != m - i){
dem++;
k++;
c[k] = i;
}
}
cout << dem << '\n';
for(ll i = 1; i <= k; i++)
cout << c[i] << ' ' << n - c[i] << '\n';
return 0;
}
- Time Complexity: O(10^6 log log 10^6 + n/2)
- Space Complexity: O(10^6)
Đây là phiên bản được chấp nhận từ contest. Tác giả dùng mảng a[] để lưu trạng thái nguyên tố (1 là nguyên tố, 0 là không phải), mảng c[] để lưu giá trị u. Code hơi thiếu comment nhưng logic đúng: sàng đến 1 triệu, rồi duyệt tìm các cặp.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n log log n + n/2) ≈ O(n) | O(n) | Brute Force với sàng nguyên tố |
| 2 | O(n log log n + n/2) ≈ O(n) | O(n) | Optimized với sàng và kiểm tra nhanh |
| 3 | O(SIEVELIMIT log log SIEVELIMIT + n/2) | O(SIEVE_LIMIT) | Tối ưu với sàng trước (Precomputation) |
| 4 | O(10^6 log log 10^6 + n/2) | O(10^6) | Phiên bản giống solutions của contest |
Bài học kinh nghiệm
- Vì u < v nên u ≤ n/2, giảm đáng kể số lần duyệt từ O(n) xuống O(n/2)
- Sàng Eratosthenes là cách hiệu quả nhất để kiểm tra tính nguyên tố cho nhiều số
- Nếu u = v (tức n chẵn và u = n/2) thì không tính, cần kiểm tra điều kiện u ≠ v
Lỗi thường gặp
- Quên kiểm tra điều kiện u ≠ v (ví dụ n=4, u=2, v=2 không được tính)
- Mảng đánh dấu nguyên tố quá nhỏ so với n (ví dụ n=300000 nhưng chỉ sàng đến 100000)
- In ra kết quả không đúng thứ tự yêu cầu (u tăng dần)
- Sử dụng kiểu dữ liệu quá nhỏ so với giới hạn của đề bài
Bình luận