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 arr) { int gcd = 0; for (int i=0;i arr = {30, 90, 15, 45, 165}; cout 输出
3
登录后复制
Example
的中文翻译为：
示例
如果有很多查询，找到数字的质因数将会重复。使用筛法，我们可以计算数字的质因数。
立即学习“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 输出
3
登录后复制
结论
我们使用了sqrt(n)方法来获取最小因子。这可以进行优化，我留给你去尝试。时间复杂度为O(sqrt(n))。在第二种方法中，时间复杂度将是筛法的时间复杂度，即O(nlog(log(n)))。请注意，我们可以根据我们设置的MAX全局变量来找到筛法的上限。
以上就是给定数组中能整除每个元素的最小整数 > 1：使用C++的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2586616.html
