Data Structure
Networking
RDBMS
Operating System
Java
MS Excel
iOS
HTML
CSS
Android
Python
C Programming
C++
C#
MongoDB
MySQL
Javascript
PHP
Physics
Chemistry
Biology
Mathematics
English
Economics
Psychology
Social Studies
Fashion Studies
Legal Studies使用 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];
// 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
更新日期： 2019-10-21
258 次观看
广告