অ্যারেটিকে এমনভাবে রূপান্তর করুন যাতে অ্যারের GCD C++ এ 1 হয়ে যায়

এই টিউটোরিয়ালে, আমরা অ্যারেকে রূপান্তর করার জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব যাতে অ্যারের GCD এক হয়ে যায়।

এর জন্য আমাদের একটি অ্যারে এবং একটি ধনাত্মক পূর্ণসংখ্যা k প্রদান করা হবে। আমাদের কাজ হল অ্যারে উপাদানগুলিকে রূপান্তর করা যাতে উপাদানগুলির GCD 1 হয় এবং শুধুমাত্র অ্যারের উপাদানগুলিকে k দ্বারা বিভক্ত করে যতক্ষণ না উপাদান k এর থেকে কম হয়৷

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
//calculating the GCD of array
int calculate_gcd(int* arr, int n){
   int gcd = arr[0];
   for (int i = 1; i < n; i++)
      gcd = __gcd(arr[i], gcd);
   return gcd;
}
//checking if the operation is possible
bool convertGcd(int* arr, int n, int k){
   int gcd = calculate_gcd(arr, n);
   int max_prime = 1;
   for (int i = 2; i <= sqrt(gcd); i++) {
      while (gcd % i == 0) {
         gcd /= i;
         max_prime = max(max_prime, i);
      }
   }
   max_prime = max(max_prime, gcd);
   return (max_prime <= k);
}
int main(){
   int arr[] = { 10, 15, 30 };
   int k = 6;
   int n = sizeof(arr) / sizeof(arr[0]);
   if (convertGcd(arr, n, k) == true)
   cout << "Yes";
   else
      cout << "No";
   return 0;
}

আউটপুট

Yes