ตรวจสอบ Array Element ที่ Coprime กับ Element อื่นๆ ทั้งหมดใน C++

สมมติมี Array A[] ของ Positive Integers โดย 2 ≤ A[i] ≤ 10⁶ ต้องการตรวจสอบว่ามี Element อย่างน้อย 1 ตัวที่เป็น Coprime กับ Element อื่นๆ ทั้งหมดหรือไม่ ตัวอย่าง Array {2, 8, 4, 10, 6, 7} ตัวเลข 7 เป็น Coprime กับตัวอื่นๆ ทั้งหมด

วิธีที่มีประสิทธิภาพ: หา Prime Factors ของทุก Integer ใน Array ถ้า Element ไหนไม่มี Common Prime Factor กับตัวอื่น จะเป็น Coprime กับทุกตัวเสมอ

ตัวอย่างโค้ด C++

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

ผลลัพธ์

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