सरणी में कम से कम एक अभाज्य संख्या वाले जोड़ों की गणना - C++

समस्या विवरण

हमें धनात्मक पूर्णांकों की एक सरणी दी गई है। लक्ष्य उन विशिष्ट जोड़ों की गणना करना है जिनमें कम से कम एक अभाज्य संख्या हो।

उदाहरण

इनपुट: arr[] = {1,2,4,8,10}

आउटपुट: 4

व्याख्या: केवल 2 अभाज्य है। जोड़े: (1,2), (2,4), (2,8), (2,10)

इनपुट: arr[] = {0,1,4,6,15}

आउटपुट: 0

व्याख्या: कोई अभाज्य संख्या नहीं।

दृष्टिकोण

सबसे बड़े तत्व तक एराटोस्थनीज की छलनी (Sieve of Eratosthenes) से अभाज्य संख्याएँ पूर्व-गणना करें। फिर सभी जोड़े जाँचें: यदि कोई तत्व अभाज्य है तो गणना बढ़ाएँ।

एल्गोरिदम

1. सरणी में अधिकतम मान temp खोजें
2. आकार temp+1 का ऐरे arr_2 बनाएँ, 0 से आरंभ करें (0=अभाज्य, 1=अभाज्य नहीं)
3. arr_2[0]=arr_2[1]=1
4. i=2 से i*i<=temp तक: यदि arr_2[i]==0 तो j=2*i से temp तक arr_2[j]=1
5. दो नेस्टेड लूप से सभी जोड़े (i,j) जाँचें: यदि arr_2[arr[i]]==0 || arr_2[arr[j]]==0 तो count++
6. count लौटाएँ

C++ कार्यान्वयन

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

void check_prime(int temp, vector& arr_2) {
    arr_2[0] = 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);
    vector arr_2(temp + 1, 0);
    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: " << Prime_Pairs(arr, size);
    return 0;
}

आउटपुट

Count: 15