C++で互いに素な配列を作成するための最小限の挿入

このセクションでは、別の興味深い問題が発生します。 N個の要素の配列があるとします。この配列を互いに素な配列にするためには、交点の最小数を見つける必要があります。互いに素な配列では、2つの連続する要素ごとのgcdは1です。配列も印刷する必要があります。

{5、10、20}のような要素があるとします。これは互いに素な配列ではありません。ここで、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