C++で他のすべてと互いに素である配列要素を確認します

正の整数の配列A[]があるとします。ここで、2 <=A [i]<=106です。iのすべての可能な値に対して。タスクは、少なくとも配列内の要素に、配列の他のすべての要素と互いに素のペアを形成する要素が存在するかどうかを確認することです。配列{2、8、4、10、6、7}について考えてみます。ここで、7は配列内の他のすべての要素と互いに素です。

この問題を解決するための効率的なアプローチは、指定された配列内の整数のすべての素因数を生成する必要があることです。要素に他の要素との共通の素因数が含まれていない場合、他の要素と互いに素のペアを常に形成します。

例

#include <iostream>
#define MAX 1000001
using namespace std;
int smallPrimeFactor[MAX];
// Hash to store prime factors count
int hash1[MAX] = { 0 };
void getSmallestPrimeFactor() {
   smallPrimeFactor[1] = 1;
   for (int i = 2; i < MAX; i++)
      smallPrimeFactor[i] = i;
   for (int i = 4; i < MAX; i += 2)
      smallPrimeFactor[i] = 2;
   for (int i = 3; i * i < MAX; i++) {
      if (smallPrimeFactor[i] == i) {
         for (int j = i * i; j < MAX; j += i)
            if (smallPrimeFactor[j] == j)
               smallPrimeFactor[j] = i;
      }
   }
}
void factorizationResult(int x) {
   int temp;
   while (x != 1) {
      temp = smallPrimeFactor[x];
      if (x % temp == 0) {
         hash1[smallPrimeFactor[x]]++;
         x = x / smallPrimeFactor[x];
      }
      while (x % temp == 0)
      x = x / temp;
   }
}
bool hasCommonFactors(int x) {
   int temp;
   while (x != 1) {
      temp = smallPrimeFactor[x];
      if (x % temp == 0 && hash1[temp] > 1)
      return false;
      while (x % temp == 0)
      x = x / temp;
   }
   return true;
}
bool hasValueToFormCoPrime(int arr[], int n) {
   getSmallestPrimeFactor();
   for (int i = 0; i < n; i++)
   factorizationResult(arr[i]);
   for (int i = 0; i < n; i++)
   if (hasCommonFactors(arr[i]))
   return true;
   return false;
}
int main() {
   int arr[] = { 2, 8, 4, 10, 6, 7 };
   int n = sizeof(arr) / sizeof(arr[0]);
   if (hasValueToFormCoPrime(arr, n))
      cout << "There is a value, that can form Co-prime pairs with all other elements";
   else
      cout << "There is no value, that can form Co-prime pairs with all other elements";
}

出力

There is a value, that can form Co-prime pairs with all other elements