计算n个数的最大公约数的最快方法是什么？
问问题
65230 次
15 回答
19
没有递归：
int result = numbers[0];
for(int i = 1; i < numbers.length; i++){
result = gcd(result, numbers[i]);
}
return result;
对于非常大的数组，使用 fork-join 模式可能会更快，您可以在其中拆分数组并并行计算 gcd。这是一些伪代码：
int calculateGCD(int[] numbers){
if(numbers.length <= 2){
return gcd(numbers);
}
else {
INVOKE-IN-PARALLEL {
left = calculateGCD(extractLeftHalf(numbers));
right = calculateGCD(extractRightHalf(numbers));
}
return gcd(left,right);
}
}
于 2011-02-03T11:39:45.680 回答
17
您可能希望先对数字进行排序，然后从最小的两个数字开始递归地计算 gcd。
于 2011-02-03T14:56:22.977 回答
3
您应该使用Lehmer 的 GCD 算法。
于 2014-11-20T10:57:51.413 回答
3
C++17
我已经编写了这个函数，用于使用 C++ 的内置函数计算 n 个数字的 gcd __gcd(int a, int b)。
int gcd(vector<int> vec, int vsize)
{
int gcd = vec[0];
for (int i = 1; i < vsize; i++)
{
gcd = __gcd(gcd, vec[i]);
}
return gcd;
}
要了解有关此功能的更多信息，请访问此链接。
另请参阅以下链接中的 Dijkstra 的 GCD 算法。它可以在没有分裂的情况下工作。所以它可能会稍微快一点（如果我错了，请纠正我。）
于 2016-07-13T07:57:57.763 回答
2
以下如何使用欧几里得算法减法：
function getGCD(arr){
let min = Math.min(...arr);
let max= Math.max(...arr);
if(min==max){
return min;
}else{
for(let i in arr){
if(arr[i]>min){
arr[i]=arr[i]-min;
}
}
return getGCD(arr);
}
}
console.log(getGCD([2,3,4,5,6]))上述实现需要 O(n^2) 时间。可以实施一些改进，但我没有绕过 n 个数字尝试这些改进。
于 2019-04-02T14:48:06.100 回答
1
如果你有很多小数字，分解实际上可能更快。
//Java
int[] array = {60, 90, 45};
int gcd = 1;
outer: for (int d = 2; true; d += 1 + (d % 2)) {
boolean any = false;
do {
boolean all = true;
any = false;
boolean ready = true;
for (int i = 0; i < array.length; i++) {
ready &= (array[i] == 1);
if (array[i] % d == 0) {
any = true;
array[i] /= d;
} else all = false;
}
if (all) gcd *= d;
if (ready) break outer;
} while (any);
}
System.out.println(gcd);
（适用于一些示例，但未经真正测试）
于 2011-02-04T14:46:58.250 回答
1
使用欧几里得算法：
function gcd(a, b)
while b ≠ 0
t := b;
b := a mod b;
a := t;
return a;
您将它应用于前两个数字，然后是第三个数字的结果，等等......：
read(a);
read(b);
result := gcd(a, b);
i := 3;
while(i <= n){
read(a)
result := gcd(result, a);
}
print(result);
于 2016-11-23T19:18:11.473 回答
1
下面是 C 程序的源代码，用于使用数组查找 N 个数字的 HCF。
#include<stdio.h>
int main()
{
int n,i,gcd;
printf("Enter how many no.s u want to find gcd : ");
scanf("%d",&n);
int arr[n];
printf("\nEnter your numbers below :- \n ");
for(i=0;i<n;i++)
{
printf("\nEnter your %d number = ",i+1);
scanf("%d",&arr[i]);
}
gcd=arr[0];
int j=1;
while(j<n)
{
if(arr[j]%gcd==0)
{
j++;
}
else
{
gcd=arr[j]%gcd;
i++;
}
}
printf("\nGCD of k no.s = %d ",gcd);
return 0;
}有关更多信息，请参阅本网站以进行进一步说明.......
于 2017-03-06T18:22:03.973 回答
1
您可以使用分而治之。要计算 gcdN([])，请将列表分为前半部分和后半部分。如果每个列表只有一个 num 。您使用 gcd2(n1, n2) 进行计算。
我刚刚写了一个快速的示例代码。（假设列表中的所有 num 都是正整数）
def gcdN(nums):
n = len(nums)
if n == 0: return "ERROR"
if n == 1: return nums[0]
if n >= 2: return gcd2(gcdN(nums[:n//2]), gcdN(nums[n//2:]))
def gcd2(n1, n2):
for num in xrange(min(n1, n2), 0, -1):
if n1 % num == 0 and n2 % num == 0:
return num
于 2017-04-05T01:43:00.730 回答
0
//Recursive solution to get the GCD of Two Numbers
long long int gcd(long long int a,long long int b)<br>
{
return b==0 ? a : gcd(b,a%b);
}
int main(){
long long int a,b;
cin>>a>>b;
if(a>b) cout<<gcd(a,b);
else cout<<gcd(b,a);
return 0;
}
于 2016-08-02T15:15:52.637 回答
0
这就是我在 Javascript 中想到的。
function calculateGCD(arrSize, arr) {
if(!arrSize)
return 0;
var n = Math.min(...arr);
for (let i = n; i > 0; i--) {
let j = 0;
while(j < arrSize) {
if(arr[j] % i === 0) {
j++;
}else {
break;
}
if(j === arrSize) {
return i;
}
}
}
}
console.log(generalizedGCD(4, [2, 6, 4, 8]));
// Output => 2
于 2020-03-25T08:13:16.847 回答
0
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
class GCDArray{
public static int [] extractLeftHalf(int [] numbers)
{
int l =numbers.length/2;
int arr[] = Arrays.copyOf(numbers, l+1);
return arr;
}
public static int [] extractRightHalf(int [] numbers)
{
int l =numbers.length/2;
int arr[] = Arrays.copyOfRange(numbers,l+1, numbers.length);
return arr;
}
public static int gcd(int[] numbers)
{
if(numbers.length==1)
return numbers[0];
else {
int x = numbers[0];
int y = numbers[1];
while(y%x!=0)
{
int rem = y%x;
y = x;
x = rem;
}
return x;
}
}
public static int gcd(int x,int y)
{
while(y%x!=0)
{
int rem = y%x;
y = x;
x = rem;
}
return x;
}
public static int calculateGCD(int[] numbers){
if(numbers.length <= 2){
return gcd(numbers);
}
else {
int left = calculateGCD(extractLeftHalf(numbers));
int right = calculateGCD(extractRightHalf(numbers));
return gcd(left,right);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
for(int i=0;i<n;i++){
arr[i]=sc.nextInt();
}
System.out.println(calculateGCD(arr));
}
}
**
以上是java工作代码..... https://stackoverflow.com/users/7412/dogbane已经提到了它的伪代码
**
于 2017-01-18T14:25:48.260 回答
0
这是一个使用 gcd(a, b, c) = gcd(a, gcd(b, c)) 属性的 gcd 方法。
它使用 BigInteger 的 gcd 方法，因为它已经过优化。
public static BigInteger gcd(BigInteger[] parts){
BigInteger gcd = parts[0];
for(int i = 1; i < parts.length; i++)
gcd = parts[i].gcd(gcd);
return gcd;
}
于 2016-05-09T21:12:54.963 回答
0
用于任意位数的递归 JavaScript (ES6) 单行。
const gcd = (a, b, ...c) => b ? gcd(b, a % b, ...c) : c.length ? gcd(a, ...c) : Math.abs(a);
于 2017-07-27T14:05:31.230 回答
-4
这是我正在寻找的答案。找到n个数字的gcd的最好方法确实是使用recursion.ie gcd(a,b,c)=gcd(gcd(a,b),c)。但是当我这样做时，我在某些程序中遇到了超时。
这里需要的优化是应该使用快速矩阵乘法算法来解决递归。
于 2011-06-03T13:51:59.117 回答