检查与C ++中所有其他元素互素的数组元素
假设我们有一个正整数数组A[]，其中2<=A[i]<=106。对于i的所有可能值。任务是检查数组中是否至少存在与数组中所有其他元素形成互质对的元素。考虑数组{2，8，4，10，6，7}。这里7与数组中的所有其他元素互质。
解决此问题的一种有效方法是，我们必须在给定数组中生成整数的所有质数因子，如果该元素与其他元素不包含任何公共质数因子，则它总是与其他元素形成互质对。
示例
#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