Đếm số nguyên tố trong mảng C++

Cho mảng số nguyên. Đếm số lượng số nguyên tố trong mảng.

Định nghĩa

Số nguyên tố: Số nguyên > 1 chỉ chia hết cho 1 và chính nó.

Ví dụ minh họa

Ví dụ 1:

• Input: arr = {1, 2, 3, 4, 5, 6, 7, 8, 9}
• Output: 4
• Giải thích: 2, 3, 5, 7 là số nguyên tố.

Ví dụ 2:

• Input: arr = {11, 12, 4, 61, 23}
• Output: 3
• Giải thích: 11, 61, 23.

Mã nguồn C++ (Kiểm tra từng số O(√n))

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

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

int main() {
    int arr[] = {1, 3, 5, 4, 8, 13, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (isPrime(arr[i])) count++;
    }
    cout << "So nguyen to trong mang: " << count;
    return 0;
}

Kết quả chạy chương trình

So nguyen to trong mang: 4

Tối ưu hóa cho nhiều truy vấn / mảng lớn - Sàng Eratosthenes

Nếu giá trị phần tử ≤ 10⁶, tiền xử lý sàng một lần O(M log log M), truy vấn O(1).

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

const int MAXV = 1000000;
vector isPrimeSieve(MAXV + 1, true);

void sieve() {
    isPrimeSieve[0] = isPrimeSieve[1] = false;
    for (int i = 2; i * i <= MAXV; i++) {
        if (isPrimeSieve[i]) {
            for (int j = i * i; j <= MAXV; j += i) {
                isPrimeSieve[j] = false;
            }
        }
    }
}

int countPrimesInArray(int arr[], int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] <= MAXV && isPrimeSieve[arr[i]]) count++;
        else if (arr[i] > MAXV) {
            // Fallback kiểm tra thủ công cho số lớn
            if (isPrime(arr[i])) count++;
        }
    }
    return count;
}

Độ phức tạp

Lưu ý

• Code gốc có bug: `return 1` nằm trong vòng lặp `for` → chỉ kiểm tra j=2. Đã sửa trong phiên bản trên.
• Tối ưu: kiểm tra 2, 3 riêng, sau đó chỉ kiểm tra dạng 6k±1.
• Với số > 10⁹, dùng Miller-Rabin deterministic.