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 次觀看
廣告