在本文中，我們給了一個整數數組，我們必須找到大於1的最小數，該數能夠整除數組中的所有元素。例如，讓我們考慮一個範例陣列[30, 90, 15, 45, 165]。
vector<int> arr = {30, 90, 15, 45, 165};
result = solve(arr);
現在我們可以找到陣列的最大公約數(GCD)。如果結果為1，這表示只有1能夠整除整個數組，我們可以返回-1或"Not possible."。如果結果是整數，那麼這個整數就能夠整除整個陣列。然而，這個整數可能不是能夠整除整個陣列的最小整數。有趣的是，這個整數的因子也能夠整除整個數組，這是有道理的。所以，如果我們能夠找到這個整數(GCD)的最小因子，我們就得到了能夠整除整個數組的最小整數。所以，簡而言之，我們需要找出陣列的最大公約數(GCD)，然後最小因子就是我們的答案。
以下的C 程式碼可以找到一個大於1的最小整數，該整數可以整除數組中的所有元素。這可以透過找到元素列表的最大公約數來實現 -
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int divisor(int x) {
if (x%2 == 0) {
return 2;
}
for (int i=3;i*i<=x;i+=2) {
if (x%i == 0) {
return i;
}
}
return x;
}
int solve(vector<int> arr) {
int gcd = 0;
for (int i=0;i<arr.size();i++) {
gcd = __gcd(gcd, arr[i]);
}
return divisor(gcd);
}
int main() {
vector<int> arr = {30, 90, 15, 45, 165};
cout << solve(arr);
return 0;
}
3
如果有很多查詢，找到數字的質因數將會重複。使用篩法，我們可以計算數字的質因數。
在C 中，找到大於1的最小數的另一種實作方法如下：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 100005;
vector<int> prime(MAX, 0);
void sieve() {
prime[0] = 1;
prime[1] = -1;
for (int i=2; i*i<MAX;i++) {
if (prime[i] == 0) {
for (int j=i*2;j<MAX;j+=i) {
if (prime[j] == 0) {
prime[j] = i;
}
}
}
}
for (int i=2; i<MAX;i++) {
if (!prime[i]) {
prime[i] = i;
}
}
}
int solve(vector<int> arr) {
int gcd = 0;
for (int i=0; i<arr.size();i++) {
gcd = __gcd(gcd, arr[i]);
}
return prime[gcd];
}
int main() {
sieve();
vector<int> arr = { 30, 90, 15, 45, 165 };
cout << solve(arr);
return 0;
}
3
我們使用了sqrt(n)方法來取得最小因子。這可以進行優化，我留給你去嘗試。時間複雜度為O(sqrt(n))。在第二種方法中，時間複雜度將是篩法的時間複雜度，即O(nlog(log(n)))。請注意，我們可以根據我們設定的MAX全域變數來找到篩法的上限。
以上是給定數組中能整除每個元素的最小整數 > 1：使用C++的詳細內容。更多資訊請關注PHP中文網其他相關文章！
