สมมติว่าเรามีอาร์เรย์ A[] ของจำนวนเต็มบวก โดยที่ 2 <=A[i] <=106 สำหรับค่าที่เป็นไปได้ทั้งหมดของ i ภารกิจคือตรวจสอบว่ามีองค์ประกอบอย่างน้อยในอาร์เรย์หรือไม่ซึ่งสร้างคู่ coprime กับองค์ประกอบอื่น ๆ ทั้งหมดของอาร์เรย์ พิจารณาอาร์เรย์ {2, 8, 4, 10, 6, 7} 7 เป็น coprime กับองค์ประกอบอื่น ๆ ทั้งหมดในอาร์เรย์
วิธีที่มีประสิทธิภาพในการแก้ปัญหานี้คือ เราต้องสร้างปัจจัยเฉพาะทั้งหมดของจำนวนเต็มในอาร์เรย์ที่กำหนด หากองค์ประกอบไม่มีปัจจัยเฉพาะร่วมกับองค์ประกอบอื่นๆ ก็จะสร้างคู่ coprime กับองค์ประกอบอื่นๆ เสมอ
ตัวอย่าง
#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
