Chuyển đổi mảng sao cho GCD của mảng trở thành 1 trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để chuyển đổi mảng sao cho GCD của mảng trở thành một.

Đối với điều này, chúng ta sẽ được cung cấp một mảng và một số nguyên dương k. Nhiệm vụ của chúng ta là chuyển đổi các phần tử mảng sao cho GCD của các phần tử là 1 trong khi chỉ chia các phần tử mảng cho k bất kỳ số lần nào cho đến khi phần tử nhỏ hơn k.

Ví dụ

#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;
}

Đầu ra

Yes