सरणी को इस प्रकार कनवर्ट करें कि सरणी का GCD C++ में 1 हो जाए

इस ट्यूटोरियल में, हम एरे को कन्वर्ट करने के लिए एक प्रोग्राम पर चर्चा करेंगे ताकि एरे का जीसीडी एक हो जाए।

इसके लिए हमें एक सरणी और एक धनात्मक पूर्णांक 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