Hướng dẫn giải của CẶP SỐ [PAIR]
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
Xác định số lượng cặp số nguyên tố (a, b) sao cho b = a + K, với a, b ∈ [2, N]. Bài toán yêu cầu đếm các số a nguyên tố sao cho a + K cũng là số nguyên tố và cả hai đều không vượt quá N.
Các cách tiếp cận
Cách Brute Force with Primality Check
#include <bits/stdc++.h>
using namespace std;
bool isPrime(int n) {
if (n < 2) return false;
for (int i = 2; i * i <= n; i++)
if (n % i == 0) return false;
return true;
}
int main() {
freopen("PAIR.inp", "r", stdin);
freopen("PAIR.out", "w", stdout);
int n, k;
cin >> n >> k;
int count = 0;
for (int i = 2; i <= n - k; i++) {
if (isPrime(i) && isPrime(i + k)) {
count++;
}
}
cout << count;
return 0;
}
- Time Complexity: O((N-K) * sqrt(N))
- Space Complexity: O(1)
Phương pháp này duyệt qua tất cả các số từ 2 đến N-K, kiểm tra mỗi số và số cách K nó có phải là số nguyên tố không bằng hàm isPrime. Hàm isPrime chạy trong O(sqrt(n)). Với N lớn (ví dụ 10^6), độ phức tạp này có thể quá chậm do kiểm tra nguyên tố lặp lại nhiều lần.
Cách Sieve of Eratosthenes Precomputation
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
bool isPrime[N];
void sieve() {
fill(isPrime, isPrime + N, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i < N; i++) {
if (isPrime[i]) {
for (int j = i * i; j < N; j += i) {
isPrime[j] = false;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
freopen("PAIR.inp", "r", stdin);
freopen("PAIR.out", "w", stdout);
int n, k;
cin >> n >> k;
sieve();
int count = 0;
for (int i = 2; i <= n - k; i++) {
if (isPrime[i] && isPrime[i + k]) {
count++;
}
}
cout << count;
return 0;
}
- Time Complexity: O(N log log N + N)
- Space Complexity: O(N)
Sử dụng sàng Eratosthenes để chuẩn bị trước mảng đánh dấu số nguyên tố cho đến N. Sau đó chỉ cần duyệt O(N) để đếm các cặp thỏa mãn. Đây là cách hiệu quả và phổ biến nhất cho giới hạn N ~ 10^6.
Cách Optimized Sieve (Early Stop)
#include <bits/stdc++.h>
using namespace std;
const int Nsieve = 1e6 + 5;
bool isPrime[Nsieve + 5];
void sieve() {
isPrime[0] = isPrime[1] = true;
for(int i = 2; i * i <= Nsieve; ++i){
if(!isPrime[i]){
for(int j = i * i; j <= Nsieve; j += i) isPrime[j] = true;
}
}
}
void Solve() {
sieve();
int n, k;
cin >> n >> k;
int cnt = 0;
for(int x = 1; x < n - k; ++x){
int y = x + k;
if(x < y && !isPrime[x] && !isPrime[y]) cnt++;
}
cout << cnt;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
freopen("PAIR.inp", "r", stdin);
freopen("PAIR.out", "w", stdout);
Solve();
return 0;
}
- Time Complexity: O(N log log N + N)
- Space Complexity: O(N)
Đây là phiên bản tối ưu của Solution 2. Biến isPrime được khởi tạo giá trị mặc định là false (không phải số nguyên tố), sau đó sàng để đánh dấu các số composite (nguyên tố == false). Vòng lặp kiểm tra chỉ chạy từ 1 đến N-K, tối ưu hơn so với Solution 1 vốn gọi hàm sqrt(N) nhiều lần.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O((N-K) * sqrt(N)) | O(1) | Brute Force with Primality Check |
| 2 | O(N log log N + N) | O(N) | Sieve of Eratosthenes Precomputation |
| 3 | O(N log log N + N) | O(N) | Optimized Sieve (Early Stop) |
Bài học kinh nghiệm
- Bài toán yêu cầu kiểm tra tính nguyên tố của nhiều số trong dãy liên tiếp, nên việc tiền xử lý bằng sàng số nguyên tố là bắt buộc để đạt hiệu năng tốt.
- Cần phải đảm bảo rằng số thứ hai (a + K) cũng nhỏ hơn hoặc bằng N.
Lỗi thường gặp
- Quên kiểm tra điều kiện a + K <= N dẫn đến truy cập ngoài mảng hoặc đếm sai.
- Khởi tạo mảng đánh dấu số nguyên tố sai (ví dụ gán true mặc định cho 0 và 1).
- Hiệu năng chậm nếu sử dụng phương pháp lặp và kiểm tra nguyên tố trực tiếp (sqrt) cho N lớn.
Bình luận