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

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

অ্যালগরিদম

diffPrimeNonPrimeSum(arr)

begin
   sum_p := sum of all prime numbers in arr
   sum_np := sum of all non-prime numbers in arr
   return |sum_p – sum_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 diffPrimeNonPrimeSum(int arr[], int n) {
   int sum_p = 0, sum_np = 0;
   for(int i = 0; i<n; i++){
      if(isPrime(arr[i])){
         sum_p += arr[i];
      } else {
         sum_np += arr[i];
      }
   }
   return abs(sum_p - sum_np);
}
main() {
   int arr[] = { 5, 8, 9, 6, 21, 27, 3, 13};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Difference: " << diffPrimeNonPrimeSum(arr, n);
}

আউটপুট

Difference: 50