Đếm cặp trong mảng có ít nhất một số nguyên tố trong C++

Cho mảng số nguyên dương. Đếm số cặp phân biệt có ít nhất một phần tử là số nguyên tố.

Ví dụ

Đầu vào − arr[] = {1,2,4,8,10}

Đầu ra − 4

Giải thích − Chỉ 2 là số nguyên tố. Các cặp: (1,2), (2,4), (2,8), (2,10).

Đầu vào − arr[] = {0,1,4,6,15}

Đầu ra − 0

Giải thích − Không có số nguyên tố.

Phương pháp giải

Dùng sàng Eratosthenes tạo mảng arr_2 đánh dấu nguyên tố (0) và không nguyên tố (1). Duyệt 2 vòng lặp qua mảng, nếu arr_2[arr[i]]==0 || arr_2[arr[j]]==0 thì count++.

• Hàm check_prime(int temp, int arr_2[]) điền sàng lên đến temp.
• Hàm Prime_Pairs(int arr[], int size):
  • Tìm temp = max_element.
  • Gọi check_prime.
  • Lặp i=0..size-1, j=i+1..size-1, kiểm tra điều kiện nguyên tố.

Ví dụ code

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

void check_prime(int temp, int arr_2[]) {
    arr_2[0] = 1; arr_2[1] = 1;
    for (int i = 2; i * i <= temp; i++) {
        if (arr_2[i] == 0) {
            for (int j = 2 * i; j <= temp; j += i) arr_2[j] = 1;
        }
    }
}

int Prime_Pairs(int arr[], int size) {
    int count = 0;
    int temp = *max_element(arr, arr + size);
    int arr_2[temp + 1];
    memset(arr_2, 0, sizeof(arr_2));
    check_prime(temp, arr_2);
    for (int i = 0; i < size; i++)
        for (int j = i + 1; j < size; j++)
            if (arr_2[arr[i]] == 0 || arr_2[arr[j]] == 0) count++;
    return count;
}

int main() {
    int arr[] = {3, 5, 2, 7, 11, 14};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of pairs in an array such that at least one element is prime are: " << Prime_Pairs(arr, size);
    return 0;
}

Đầu ra

Count of pairs in an array such that at least one element is prime are: 15