C++에서 배열의 GCD가 1이 되도록 배열을 변환합니다.

이 튜토리얼에서는 배열의 GCD가 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