Tìm số cặp số nguyên tố trong mảng bằng C++

Cho mảng arr[], đếm số cặp (i, j) với i < j sao cho cả arr[i] và arr[j] đều là số nguyên tố.

Ví dụ

Input: arr[] = {1, 2, 3, 5, 7, 9} Output: 6
Các cặp: (2,3), (2,5), (2,7), (3,5), (3,7), (5,7)

Input: arr[] = {1, 4, 5, 9, 11} Output: 1

Phương pháp Brute Force

Dùng Sieve đánh dấu nguyên tố, sau đó 2 vòng lặp lồng nhau kiểm tra tất cả cặp. Độ phức tạp O(N²).

Mã nguồn Brute Force

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

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

int main() {
    int arr[] = {1, 2, 3, 5, 7, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int answer = 0;
    int MAX = *max_element(arr, arr + n);
    bool prime[n];
    seiveOfEratosthenes(arr, prime, n, MAX);

    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
            if (prime[i] && prime[j])
                answer++;
    cout << answer << "\n";
    return 0;
}

Kết quả

6

Phương pháp hiệu quả (Công thức tổ hợp)

Đếm tổng số phần tử nguyên tố trong mảng = cnt. Số cặp = C(cnt, 2) = cnt * (cnt - 1) / 2. Độ phức tạp O(N).

Mã nguồn hiệu quả

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

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

int main() {
    int arr[] = {1, 2, 3, 5, 7, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int answer = 0;
    int MAX = *max_element(arr, arr + n);
    bool prime[n];
    seiveOfEratosthenes(arr, prime, n, MAX);

    for (int i = 0; i < n; i++)
        if (prime[i]) answer++;
    answer = answer * (answer - 1) / 2;
    cout << answer << "\n";
    return 0;
}

Kết quả

6

Giải thích

Sieve tạo mảng boolean đánh dấu nguyên tố. Đếm số lượng nguyên tố cnt, áp dụng công thức tổ hợp C(cnt, 2). Giảm độ phức tạp từ O(N²) xuống O(N).

Kết luận

Bài viết trình bày 2 cách đếm cặp nguyên tố: Brute Force O(N²) và công thức tổ hợp O(N) sau khi dùng Sieve. Mã C++ đầy đủ, dễ hiểu, áp dụng được cho các ngôn ngữ khác.