নন-প্রাইম সংখ্যার গুণফল এবং একটি অ্যারের মৌলিক সংখ্যার মধ্যে পরম পার্থক্য?

এখানে আমরা দেখব কিভাবে আমরা একটি অ্যারের সমস্ত মৌলিক সংখ্যা এবং সমস্ত নন-প্রাইম সংখ্যার গুণফলের মধ্যে পরম পার্থক্য খুঁজে পেতে পারি। এই সমস্যা সমাধানের জন্য, আমাদের একটি সংখ্যা মৌলিক কি না তা পরীক্ষা করতে হবে। প্রাইমালিটি পরীক্ষার একটি সম্ভাব্য উপায় হল একটি সংখ্যা পরীক্ষা করা যে সংখ্যাটি 2 থেকে বর্গমূলের মধ্যে কোনো সংখ্যা দ্বারা বিভাজ্য নয়। সুতরাং এই প্রক্রিয়াটি 𝑂(√𝑛) পরিমাণ সময় নেবে। তারপর পণ্যটি পান এবং পরম পার্থক্য খুঁজে বের করার চেষ্টা করুন।

অ্যালগরিদম

diffPrimeNonPrimeProd(arr)

begin
   prod_p := product of all prime numbers in arr
   prod_np := product of all non-prime numbers in arr
   return |prod_p – prod_np|
end

উদাহরণ

#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(int n){
   for(int i = 2; i<=sqrt(n); i++){
      if(n % i == 0){
         return false; //not prime
      }
   }
   return true; //prime
}
int diffPrimeNonPrimeProd(int arr[], int n) {
   int prod_p = 1, prod_np = 1;
   for(int i = 0; i<n; i++){
      if(isPrime(arr[i])){
         prod_p *= arr[i];
      } else {
         prod_np *= arr[i];
      }
   }
   return abs(prod_p - prod_np);
}
main() {
   int arr[] = { 4, 5, 3, 8, 13, 10};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Difference: " << diffPrimeNonPrimeProd(arr, n);
}

আউটপুট

Difference: 125