C++-এ অ্যারেতে অন্তত একটি প্রাইম থাকা জোড়া সংখ্যা গণনা

আমাদের একটি পজিটিভ ইন্টিজার অ্যারে দেওয়া আছে। লক্ষ্য হল এমন স্বতন্ত্র জোড়া বের করা যাতে জোড়া-র অন্তত একটি সদস্য প্রাইম সংখ্যা।

উদাহরণ

ইনপুট: arr[] = {1,2,4,8,10}

আউটপুট: ৪

ব্যাখ্যা: একমাত্র প্রাইম ২। এর সাথে অন্যগুলোর জোড়া: (1,2), (2,4), (2,8), (2,10)।

ইনপুট: arr[] = {0,1,4,6,15}

আউটপুট: ০

ব্যাখ্যা: কোনো প্রাইম নেই।

অ্যালগরিদম (Sieve of Eratosthenes)

1. অ্যারে এবং আকার ইনপুট নিন।
2. ম্যাক্সিমাম এলিমেন্ট বের করুন।
3. সেই ম্যাক্সিমাম পর্যন্ত Sieve দিয়ে প্রাইম চিহ্নিত করুন (arr_2[i]=0 মানে প্রাইম)।
4. নেস্টেড লুপে সব জোড়া চেক করুন: যদি arr_2[arr[i]]==0 বা arr_2[arr[j]]==0 হয় তবে কাউন্ট বাড়ান।

C++ বাস্তবায়ন

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

void check_prime(int temp, int 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.data());
    
    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;
}

আউটপুট

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