c - 找到两个数字的 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 的常规方法，据我所知，这是迄今为止找到 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 3

对于小数，请使用二进制 GCD（欧几里德的 GCD 算法更快），对于大数，请尝试 Lehmer 算法。

二进制 GCD：https ://www.google.com/amp/s/www.geeksforgeeks.org/steins-algorithm-for-finding-gcd/amp/

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 %d\n",a1,b1,a);
   printf("LCM of %d and %d is %d",a1,b1,(a1*b1/a));
}