给定数组中能整除每个元素的最小整数

给定数组中能整除每个元素的最小整数 > 1：使用c++

在本文中，我们给出了一个整数数组，并且我们必须找到大于1的最小数，该数能够整除数组中的所有元素。例如，让我们考虑一个示例数组[30, 90, 15, 45, 165]。

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

现在我们可以找到数组的最大公约数(GCD)。如果结果为1，这意味着只有1能够整除整个数组，我们可以返回-1或者"Not possible."。如果结果是一个整数，那么这个整数能够整除整个数组。然而，这个整数可能不是能够整除整个数组的最小整数。有趣的是，这个整数的因子也能够整除整个数组，这是有道理的。所以，如果我们能够找到这个整数(GCD)的最小因子，我们就得到了能够整除整个数组的最小整数。所以，简而言之，我们需要找到数组的最大公约数(GCD)，然后最小因子就是我们的答案。

Example

的中文翻译为：

示例

以下的C++代码可以找到一个大于1的最小整数，该整数可以整除数组中的所有元素。这可以通过找到元素列表的最大公约数来实现 -

#include 
#include 
#include 
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 arr) {
   int gcd = 0;
   for (int i=0;i arr = {30, 90, 15, 45, 165};
   cout << solve(arr);
   return 0;
}

输出

Example

的中文翻译为：

示例

如果有很多查询，找到数字的质因数将会重复。使用筛法，我们可以计算数字的质因数。

Civitai

AI艺术分享平台！海量SD资源和开源模型。

下载

立即学习“C++免费学习笔记（深入）”；

在C++中，找到大于1的最小数的另一种实现方法如下：

#include 
#include 
#include 
using namespace std;
const int MAX = 100005;
vector prime(MAX, 0);
void sieve() {
   prime[0] = 1;
   prime[1] = -1;
   for (int i=2; i*i arr) {
   int gcd = 0;
   for (int i=0; i arr = { 30, 90, 15, 45, 165 };
   cout << solve(arr);
   return 0;
}