首页 > 后端开发 > C++ > 给定数组中能整除每个元素的最小整数 > 1:使用C++

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

WBOY
发布: 2023-08-26 21:53:12
转载
744 人浏览过

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

在本文中,我们给出了一个整数数组,并且我们必须找到大于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),然后最小因子就是我们的答案。

Example

的中文翻译为:

示例

以下的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
登录后复制
登录后复制

Example

的中文翻译为:

示例

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

在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中文网其他相关文章!

来源:tutorialspoint.com
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板