Kiểm tra một phần tử mảng là nguyên tố với tất cả các phần tử khác trong C ++

Giả sử chúng ta có một mảng A [] các số nguyên dương, trong đó 2 <=A [i] <=106. Với tất cả các giá trị có thể có của i. Nhiệm vụ là kiểm tra xem có tồn tại ít nhất trên phần tử trong mảng, có tạo thành cặp nguyên tố với tất cả các phần tử khác của mảng hay không. Xét mảng {2, 8, 4, 10, 6, 7}. Đây là số 7 cùng chuẩn với tất cả các phần tử khác trong mảng.

Một cách tiếp cận hiệu quả để giải quyết vấn đề này là chúng ta phải tạo ra tất cả các thừa số nguyên tố của các số nguyên trong mảng đã cho, nếu phần tử không chứa bất kỳ thừa số nguyên tố chung nào với các phần tử khác, nó luôn tạo thành cặp nguyên tố với các phần tử khác.

Ví dụ

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

Đầu ra

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