C++-তে অ্যারেতে থাকা সব প্রাইম নম্বরের গুণফল বের করা

একটি ইন্টিজার অ্যারে arr[] দেওয়া আছে। টাস্ক হলো সেটি থেকে সব প্রাইম নম্বরের গুণফল বের করা।

প্রাইম নম্বর হলো যেসব নম্বর শুধু ১ এবং নিজের দ্বারা বিভাজ্য (যেমন ২, ৩, ৫, ৭, ১১...)। নোট: ১ প্রাইম নম্বর নয়।

ইনপুট − arr[] = {11, 20, 31, 4, 5, 6, 70}

আউটপুট − 1705

ব্যাখ্যা − প্রাইম নম্বর: ১১, ৩১, ৫। গুণফল = ১৭০৫।

ইনপুট − arr[] = {1, 2, 3, 4, 5, 6, 7}

আউটপুট − 210

ব্যাখ্যা − প্রাইম নম্বর: ২, ৩, ৫, ৭ (১ প্রাইম নয়)। গুণফল = ২১০।

প্রোগ্রামে ব্যবহৃত পদ্ধতি (Sieve of Eratosthenes)

অ্যারের সর্বোচ্চ ভ্যালু বের করুন (max_val)।
max_val পর্যন্ত সিভ (Sieve) ব্যবহার করে সব প্রাইম নম্বর চিহ্নিত করুন।
অ্যারে ট্রাভার্স করে প্রাইম এলিমেন্টগুলোর গুণফল বের করুন।

অ্যালগরিদম

Start
In function prodprimearr(arr[], n)
  Step 1: max_val = max_element(arr, arr+n)
  Step 2: vector isprime(max_val+1, true)
  Step 3: isprime[0] = isprime[1] = false
  Step 4: for p=2 to sqrt(max_val)
            if isprime[p] true then
              for i=p*2 to max_val step p
                isprime[i] = false
  Step 5: prod = 1
  Step 6: for i=0 to n-1
            if isprime[arr[i]] then prod *= arr[i]
  Step 7: return prod
Stop

উদাহরণ

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

int prodprimearr(int arr[], int n) {
    int max_val = *max_element(arr, arr + n);
    vector isprime(max_val + 1, true);
    isprime[0] = false;
    isprime[1] = false;
    for (int p = 2; p * p <= max_val; p++) {
        if (isprime[p]) {
            for (int i = p * 2; i <= max_val; i += p)
                isprime[i] = false;
        }
    }
    int prod = 1;
    for (int i = 0; i < n; i++)
        if (isprime[arr[i]])
            prod *= arr[i];
    return prod;
}

int main() {
    int arr[] = {11, 20, 31, 4, 5, 6, 70};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << prodprimearr(arr, n);
    return 0;
}