C++에서 다른 모든 요소와 동소인 배열 요소를 확인하십시오.

2 <=A[i] <=106인 양의 정수 배열 A[]가 있다고 가정합니다. 가능한 모든 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