Hiểu bài toán

Xác định số lượng cặp số nguyên tố (p, q) trong khoảng từ 1 đến n sao cho q - p = k. Ví dụ: với n=17, k=2, các cặp sinh đôi là (3,5), (5,7), (11,13).

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

Cách Brute Force (Kiểm tra chéo)

#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() {
    int n, k;
    cin >> n >> k;
    int count = 0;
    for (int i = 1; i <= n - k; i++) {
        if (isPrime(i) && isPrime(i + k)) {
            count++;
        }
    }
    cout << count;
    return 0;
}

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

Duyệt qua tất cả các số p từ 1 đến n - k. Với mỗi p, kiểm tra xem p và p + k có phải là số nguyên tố không bằng hàm isPrime (kiểm tra thủ công các ước). Nếu cả hai đều nguyên tố thì tăng biến đếm.

Cách Sàng Eratosthenes (Prime Sieve)

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

const int MAX = 1000001;
int a[MAX];

void sieve() {
    fill(a, a + MAX, 1);
    a[0] = a[1] = 0;
    for (int i = 2; i * i < MAX; i++) {
        if (a[i]) {
            for (int j = i * i; j < MAX; j += i) {
                a[j] = 0;
            }
        }
    }
}

int main() {
    sieve();
    int n, k;
    cin >> n >> k;
    int count = 0;
    for (int p = 1; p <= n - k; p++) {
        if (a[p] && a[p + k]) {
            count++;
        }
    }
    cout << count;
    return 0;
}

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

Sử dụng thuật toán sàng Eratosthenes để tạo một mảng đánh dấu các số nguyên tố trong phạm vi [0, n]. Sau đó, chỉ cần duyệt từ 1 đến n-k, tra cứu mảng đã sàng để kiểm tra tính nguyên tố của p và p+k. Đây là cách tiếp cận chuẩn cho các bài toán số học với giới hạn dữ liệu vừa phải.

Cách Sàng Eratosthenes (Tối ưu)

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

const int MAX = 1000001;
bool is_prime[MAX];

void sieve() {
    fill(is_prime, is_prime + MAX, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i < MAX; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < MAX; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    sieve();

    int n, k;
    cin >> n >> k;

    int count = 0;
    for (int i = 1; i <= n - k; ++i) {
        if (is_prime[i] && is_prime[i + k]) {
            ++count;
        }
    }

    cout << count << endl;
    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 Approach 2. Sử dụng mảng boolean is_prime (hoặc char để tăng tốc độ truy cập bộ nhớ). Áp dụng chuẩn I/O nhanh (ios_base::sync_with_stdio(false)). Logic vẫn là sàng nguyên tố trước, sau đó đếm các cặp (i, i+k) thỏa mãn.

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

Bài học kinh nghiệm

• Bài toán quy về việc kiểm tra tính nguyên tố của các số trong một khoảng.
• Với giới hạn N ≤ 10^6, thuật toán sàng Eratosthenes là lựa chọn tối ưu để precompute (tiền tính) các số nguyên tố.
• Sau khi có mảng đánh dấu nguyên tố, việc đếm cặp chỉ là một vòng lặp đơn giản O(N).

Lỗi thường gặp

• Sử dụng thuật toán kiểm tra nguyên tố trực tiếp (trial division) cho từng số trong vòng lặp lặp lại nhiều lần sẽ dẫn đến Time Limit Exceeded (TLE) với N lớn.
• Quên kiểm tra điều kiện biên (ví dụ: p >= 1, q <= n).
• Sử dụng biến int cho mảng lớn hoặc phép nhân i * i trong vòng lặp sàng có thể gây tràn số nếu không dùng long long hoặc cẩn thận.