Số lần chèn tối thiểu để tạo một mảng Co-nguyên tố trong C ++

Trong phần này chúng ta sẽ thấy một vấn đề thú vị khác. Giả sử chúng ta có một mảng gồm N phần tử. Chúng ta phải tìm số giao điểm tối thiểu để làm cho mảng này là mảng đồng nguyên tố. Trong mảng đồng nguyên tố, gcd của mỗi hai phần tử liên tiếp là 1. Chúng ta cũng phải in mảng.

Giả sử chúng ta có các phần tử như {5, 10, 20}. Đây không phải là mảng đồng nguyên tố. Bây giờ bằng cách chèn 1 vào giữa 5, 10 và 10, 20, nó sẽ là mảng đồng nguyên tố. Vì vậy, mảng sẽ giống như {5, 1, 10, 1, 20}

Thuật toán

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

Ví dụ

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

Đầu ra

Number of intersection points: 1
2 7 1 28