大于 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

开启你的职业生涯

完成课程获得认证

开始学习
广告