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

Cho mảng A[] số nguyên dương (2 ≤ A[i] ≤ 10⁶). Kiểm tra xem có ít nhất một phần tử tạo cặp cùng nguyên tố (coprime) với tất cả các phần tử còn lại hay không. Ví dụ mảng {2, 8, 4, 10, 6, 7} → 7 cùng nguyên tố với tất cả.

Cách hiệu quả: tìm tất cả thừa số nguyên tố của các phần tử trong mảng. Nếu một phần tử không chia sẻ thừa số nguyên tố nào với phần tử khác thì nó tạo cặp coprime với tất cả.

Ví dụ

#include <iostream>
#define MAX 1000001
using namespace std;

int smallPrimeFactor[MAX];
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";
}

Kết quả

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