找出两个数的GCD的最快方法是什么?

Question

我有一个大小为n的数组。我需要找到具有给定数字的每个元素的GCD，如果它大于1，则将其添加到另一个数组。最快的方法是什么?

Answer 1

int gcd(int a, int b)
{
    if(b == 0) {
            return a;
    }
    else {
        return gcd(b, a % b);
    }
}

Answer 2

对于小数使用二进制GCD(这是更快的欧几里德的GCD算法)&对于大数，试试Lehmer算法。

二进制GCD: https://www.geeksforgeeks.org/steins-algorithm-for-finding-gcd/

Answer 3

下面的代码使用了我们人类用来计算GCD的正常方法，并且是迄今为止，根据我的说法，找到2个数字的GCD(HCF)的最快方法:

#include <iostream>
using namespace std;
int main()
{
    int N1;
    int N2;
    cin<<N1;
    cin<<N2;
    int small=N1;
    int big=N2;
    if (N1>N2){
        N1=small;
        N2=big;
    }
    int P=1;
    int i=1;
    while (i<=N1){
        if (N1%i==0 && N2%i==0){
            N1=N1/i;
            N2=N2/i;
            P=P*i;
            i=1;
        }
        i=i+1;
    }
    cout<<"GCD= "<<P;
    return 0;
}

Answer 4

#include<stdio.h>
int main()
{
   int a,b,a1,b1;
   printf("Enter two numbers:");
   scanf("%d%d",&a,&b);
   a1=a;b1=b;
   while(a!=b)
   {
      if(a>b)
        a=a-b;
      else
        b=b-a;
   }
   printf("GCD of %d and %d is %dn",a1,b1,a);
   printf("LCM of %d and %d is %d",a1,b1,(a1*b1/a));
}