Tìm số số nguyên tố trong mảng con (subarray) bằng C++

Cho mảng arr[] và q truy vấn, mỗi truy vấn cho khoảng [L, R]. Đếm số nguyên tố trong arr[L..R].

Ví dụ

Input: arr[] = {1,2,3,4,5,6}, q=1, L=0, R=3 Output: 2 (số nguyên tố: 2,3)
Input: arr[] = {2,3,5,8,12,11}, q=1, L=0, R=5 Output: 4 (2,3,5,11)

Phương pháp Brute Force

Với mỗi truy vấn, duyệt từ L đến R, kiểm tra nguyên tố bằng thử chia. Độ phức tạp O(Q·N·√N).

Mã nguồn Brute Force

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

bool isPrime(int N) {
    if (N <= 1) return false;
    if (N <= 3) return true;
    if (N % 2 == 0 || N % 3 == 0) return false;
    for (int i = 5; i * i <= N; i += 2)
        if (N % i == 0) return false;
    return true;
}

int main() {
    int N = 6;
    int arr[N] = {1, 2, 3, 4, 5, 6};
    int Q = 1;
    while (Q--) {
        int L = 0, R = 3;
        int cnt = 0;
        for (int i = L; i <= R; i++)
            if (isPrime(arr[i])) cnt++;
        cout << cnt << "\n";
    }
    return 0;
}

Kết quả

2

Phương pháp hiệu quả (Sieve of Eratosthenes)

Tiền xử lý: dùng sàng Eratosthenes tìm tất cả số nguyên tố ≤ max(arr). Tạo mảng boolean isPrime[] đánh dấu từng phần tử của arr. Mỗi truy vấn chỉ duyệt L..R và đếm isPrime[i]. Độ phức tạp: tiền xử lý O(MAX log log MAX), mỗi truy vấn O(N), tổng O(Q·N).

Mã nguồn hiệu quả

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

vector<bool> sieveOfEratosthenes(int *arr, int n, int MAX) {
    vector<bool> p(n);
    vector<bool> Prime(MAX + 1, true);
    Prime[0] = Prime[1] = false;
    for (int p = 2; p * p <= MAX; p++)
        if (Prime[p])
            for (int i = p * 2; i <= MAX; i += p)
                Prime[i] = false;
    for (int i = 0; i < n; i++)
        p[i] = Prime[arr[i]];
    return p;
}

int main() {
    int n = 6;
    int arr[n] = {1, 2, 3, 4, 5, 6};
    int MAX = *max_element(arr, arr + n);
    vector<bool> isprime = sieveOfEratosthenes(arr, n, MAX);

    int q = 1;
    while (q--) {
        int L = 0, R = 3;
        int cnt = 0;
        for (int i = L; i <= R; i++)
            if (isprime[i]) cnt++;
        cout << cnt << "\n";
    }
    return 0;
}

Kết quả

2

Giải thích

Sàng Eratosthenes đánh dấu hợp số bằng cách loại bội của các số nguyên tố. Sau đó tra cứu O(1) cho mỗi phần tử mảng. Phù hợp cho nhiều truy vấn.

Kết luận

Bài viết so sánh Brute Force O(Q·N·√N) và phương pháp Sieve O(MAX log log MAX + Q·N). Mã C++ đầy đủ cho cả hai cách. Có thể áp dụng cho C, Java, Python.