大於 1 的最小整數，它能整除給定陣列中的每個元素：使用 C++

在本文中，我們得到一個數組中的整數，我們必須找到大於 1 的最小數字，該數字能整除陣列中的所有元素。例如，讓我們考慮一個示例陣列 [30, 90, 15, 45, 165]。

vector<int> arr = {30, 90, 15, 45, 165};
result = solve(arr);

現在我們可以找到陣列的 GCD（最大公約數）。如果結果為 1，則意味著只有 1 能整除整個陣列，我們可以返回 -1 或“不可能”。如果它是一個整數，則該整數能整除整個陣列。但是，該整數可能不是能整除整個陣列的最小整數。有趣的是，該整數的因子也能整除整個陣列，這是有道理的。因此，如果我們能找到該整數（GCD）的最小因子，我們就能得到能整除整個陣列的最小整數。因此，簡而言之，我們需要找到陣列的 GCD，然後 GCD 的最小因子就是我們的答案。

示例

以下 C++ 程式碼查詢大於 1 的最小整數，該整數能整除陣列的所有元素。這可以透過查詢元素列表的 GCD 來完成：

#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 全域性變數設定的限制範圍內的篩法。

更新於：2022年8月10日

瀏覽量：195

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告