Hiểu bài toán

Bài toán yêu cầu đếm số lượng số nguyên tố trong khoảng cách [L, R] với nhiều truy vấn khác nhau. Với mỗi bộ test gồm L và R, cần trả về số lượng số nguyên tố từ L đến R (giá trị L, R ≤ 10^6). Do có nhiều truy vấn (T ≤ 100) và L, R có thể thay đổi, cần một phương pháp tối ưu để xử lý nhanh.

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

Cách Sàng Eratosthenes với mảng đếm tiền tố (Prefix Sum)

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#define MAX 1000000

int prime[MAX+1];
int cntPrime[MAX+1];

void sang(int n) {
    for (int i = 0; i <= n; i++) {
    prime[i] = 1;
    }
    prime[0] = prime[1] = 0;
    for (int i = 2; i * i <= n; i++)
        if (prime[i])
            for (int j = i * i; j <= n; j += i)
                prime[j] = 0;

    cntPrime[0] = 0;
    for (int i = 1; i <= n; i++)
        cntPrime[i] = cntPrime[i-1] + prime[i];
}
int main() {
    int t,l,r;
    scanf("%d",&t);
    sang(MAX);
    for (int i = 0;i < t;i++){
        scanf("%d %d",&l,&r);
        printf("%d\n",cntPrime[r]-cntPrime[l-1]);
    }
    return 0;
}

• Time Complexity: O(N log log N) tiền xử lý + O(1) mỗi truy vấn
• Space Complexity: O(N)

Phương pháp này sử dụng sàng Eratosthenes để tìm tất cả số nguyên tố lên đến 10^6. Sau đó, xây dựng mảng đếm tiền tố (prefix sum) cntPrime trong đó cntPrime[i] là số lượng số nguyên tố từ 1 đến i. Với mỗi truy vấn [L, R], kết quả là cntPrime[R] - cntPrime[L-1]. Đây là cách tiếp cận tối ưu nhất cho các ràng buộc của bài toán.

Cách Sàng Eratosthenes cơ bản (C++ Vector)

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const int MAX = 1e6;
vector<bool> isPrime(MAX + 1, true);
vector<int> prefix(MAX + 1, 0);

void sieve() {
    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;
            }
        }
    }
    for (int i = 1; i <= MAX; ++i) {
        prefix[i] = prefix[i - 1] + (isPrime[i] ? 1 : 0);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    sieve();
    int T;
    cin >> T;
    while (T--) {
        int L, R;
        cin >> L >> R;
        cout << prefix[R] - prefix[L - 1] << "\n";
    }
    return 0;
}

• Time Complexity: O(N log log N) tiền xử lý + O(1) mỗi truy vấn
• Space Complexity: O(N)

Tương tự như cách tiếp cận bằng C, nhưng sử dụng vector<bool> của C++ để tiết kiệm bộ nhớ và cú pháp tiện lợi hơn. Logic vẫn giữ nguyên: tạo mảng đánh dấu số nguyên tố và mảng tổng tiền tố để trả lời truy vấn ngay lập tức.

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

Bài học kinh nghiệm

• Cần tiền xử lý trước bằng thuật toán sàng để giảm thời gian xử lý các truy vấn từ O(R) xuống O(1).
• Sử dụng mảng tổng tiền tố (Prefix Sum Array) để tính số lượng phần tử trong một đoạn con của mảng một cách nhanh chóng.

Lỗi thường gặp

• Không kiểm tra ranh giới L, R khi tính toán prefix sum (ví dụ: L=1 thì L-1=0 cần có giá trị hợp lệ).
• Sử dụng thuật toán kiểm tra số nguyên tố cho từng số trong đoạn [L, R] thay vì sàng sẽ dẫn đến Timeout do độ phức tạp quá cao.