Hiểu bài toán

Cho hai số nguyên dương N và K. Đếm số lượng cặp số nguyên dương (x, y) sao cho: 1 ≤ x < y ≤ N, y - x = K, và cả x và y đều là số nguyên tố. Nói cách khác, cần tìm số cặp số nguyên tố cách nhau đúng K đơn vị trong khoảng từ 1 đến N.

Các cách tiếp cận

Cách Brute Force (Kiểm tra từng cặp)

#include <bits/stdc++.h>
using namespace std;

bool ktnt(long long n) {
    if (n <= 1) return 0;
    if (n == 2 || n == 3) return 1;
    if (n % 2 == 0 || n % 3 == 0) return 0;
    for (int i = 5; i <= sqrt(n); i += 6)
        if (n % i == 0 || n % (i + 2) == 0) return 0;
    return 1;
}

int main() {
    freopen("pair.inp", "r", stdin);
    freopen("pair.out", "w", stdout);
    long long n, k;
    cin >> n >> k;
    long long count = 0;
    // Duyệt qua các số x từ 1 đến n - k
    for (long long x = 1; x <= n - k; x++) {
        if (ktnt(x) && ktnt(x + k)) {
            count++;
        }
    }
    cout << count;
    return 0;
}

• Time Complexity: O(N * sqrt(N))
• Space Complexity: O(1)

Phương pháp này duyệt qua tất cả các số x từ 1 đến N - K. Với mỗi x, nó kiểm tra xem x có phải là số nguyên tố không (sử dụng hàm ktnt) và xem x + K có phải là số nguyên tố không. Nếu cả hai đều là số nguyên tố, ta tăng biến đếm. Hàm ktnt kiểm tra tính nguyên tố trong thời gian O(sqrt(n)). Do đó, độ phức tạp tổng thể là O(N * sqrt(N)).

Cách Sàng Eratosthenes

#include <bits/stdc++.h>
using namespace std;

int main() {
    ifstream fin("pair.inp");
    ofstream fout("pair.out");

    int N, K;
    fin >> N >> K;

    vector<bool> isPrime(N + 1, true);
    isPrime[0] = isPrime[1] = false;

    // Sàng Eratosthenes để tìm tất cả các số nguyên tố <= N
    for (int i = 2; i * i <= N; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= N; j += i)
                isPrime[j] = false;
        }
    }

    long long count = 0;
    // Duyệt từ x = 2 đến N - K
    for (int x = 2; x + K <= N; x++) {
        if (isPrime[x] && isPrime[x + K]) {
            count++;
        }
    }

    fout << count << "\n";
    return 0;
}

• Time Complexity: O(N log log N)
• Space Complexity: O(N)

Thay vì kiểm tra tính nguyên tố cho mỗi số lặp lại, ta sử dụng thuật toán sàng Eratosthenes để tạo một mảng boolean 'isPrime' trong đó 'isPrime[i]' là true nếu i là số nguyên tố. Quá trình sàng mất O(N log log N). Sau đó, ta chỉ cần duyệt từ 2 đến N - K và kiểm tra điều kiện trong O(1) bằng cách truy cập mảng. Đây là cách tiếp cận hiệu quả và phổ biến nhất.

Cách Tối ưu hóa Sàng (Cải tiến)

#include <bits/stdc++.h>
#define ll long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
using namespace std;

const int MAX = 1e6 + 1;
int p[MAX];

void sang() {
    FOR(i, 0, MAX) p[i] = 1;
    p[0] = p[1] = 0;
    for (int i = 2; i * i <= MAX; i++) {
        if (p[i]) {
            for (int j = i * i; j <= MAX; j += i) p[j] = 0;
        }
    }
}

int main() {
    freopen("pair.inp", "r", stdin);
    freopen("pair.out", "w", stdout);
    int n, k; cin >> n >> k;
    sang();
    int dem = 0;
    FOR(i, 1, n - k) {
        int tar = k + i;
        if (tar >= 1 && tar <= n && p[i] && p[tar]) dem++;
    }
    cout << dem;
    return 0;
}

• Time Complexity: O(MAX log log MAX + N)
• Space Complexity: O(MAX)

Đây là biến thể của phương pháp sàng Eratosthenes. Code định nghĩa một mảng toàn cục 'p' có kích thước cố định MAX (1e6 + 1). Hàm 'sang()' thực hiện sàng một lần. Trong hàm chính, sau khi đọc N và K, code duyệt các số i từ 1 đến N-K và kiểm tra mảng p. Phương pháp này giống với Approach 2 nhưng khai báo mảng tĩnh toàn cục và thường được tối ưu hóa cho tốc độ chạy (dùng mảng int thay vì vector bool).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể giảm độ phức tạp từ O(N * sqrt(N)) xuống O(N log log N) bằng cách tách biệt quá trình tạo danh sách số nguyên tố và quá trình đếm cặp.
• Sàng Eratosthenes là công cụ phù hợp nhất cho các bài toán yêu cầu kiểm tra tính nguyên tố của nhiều số trong một khoảng giá trị liên tiếp.
• Với ràng buộc N có thể lên tới 10^6, việc sử dụng mảng tĩnh (static array) hoặc vector với kích thước đủ lớn là cần thiết.

Lỗi thường gặp

• Bỏ qua số nguyên tố 2 khi duyệt (nên bắt đầu từ x = 2 hoặc x = 1 và kiểm tra điều kiện).
• Xử lý sai giới hạn vòng lặp: vòng lặp chỉ cần chạy đến N - K.
• Quên kiểm tra điều kiện x + K <= N trong vòng lặp hoặc điều kiện tar <= n trong code.
• Sử dụng biến kiểu int cho N và K lớn (ví dụ > 10^5) có thể gây tràn số nếu tính toán cẩn thận, nhưng trong bài này N <= 10^6 nên int vẫn an toàn.