C++에서 Co-prime 배열을 만들기 위한 최소 삽입

이 섹션에서 우리는 또 다른 흥미로운 문제를 볼 것입니다. N개의 요소로 구성된 배열이 있다고 가정합니다. 이 배열을 co-prime 배열로 만들기 위해서는 최소한의 교차점을 찾아야 합니다. co-prime 배열에서 모든 두 연속 요소의 gcd는 1입니다. 배열도 인쇄해야 합니다.

{5, 10, 20}과 같은 요소가 있다고 가정합니다. 이것은 co-prime 배열이 아닙니다. 이제 5, 10과 10, 20 사이에 1을 삽입하면 공소수 배열이 됩니다. 따라서 배열은 {5, 1, 10, 1, 20}

알고리즘

makeCoPrime(arr, n):
begin
   count := 0
   for i in range 1 to n, do
      if gcd of arr[i] and arr[i – 1] is not 1, then increase count by 1
   done
   display count value
   display the first element of arr
   for i in range 1 to n, do
      if gcd of arr[i] and arr[i – 1] is not 1, then display 1
   display element arr[i]
   done
end

예시

#include <iostream>
#include <algorithm>
using namespace std;
int makeCoPrime(int arr[], int n){
   int count = 0;
   for(int i = 1; i<n; i++){
      if(__gcd(arr[i], arr[i - 1]) != i){
         count++;
      }
   }
   cout << "Number of intersection points: " << count << endl;
   cout << arr[0] << " ";
   for(int i = 1; i<n; i++){
      if(__gcd(arr[i], arr[i - 1]) != i){
         cout << 1 << " ";
      }
      cout << arr[i] << " ";
   }
}
int main() {
   int A[] = {2, 7, 28};
   int n = sizeof(A)/sizeof(A[0]);
   makeCoPrime(A, n);
}

출력

Number of intersection points: 1
2 7 1 28