Question

跪求一段求最大公约数的C语言算法

Answer 1

#include <stdio.h>
int gcd (int a,int b)
{
if (!b) return a;
return gcd (b,a%b);
}
int main ()
{
int a, b ;
scanf ("%d %d",&a,&b);
printf ("%d\n",gcd (a,b));
}
这个就是数论上经典的用殴几里德算法求最大公约数。其时间复杂度约为7*min (a,b).它还有一个就是碾转相除法来解。

Answer 2

#include <stdio.h>
#include <stdarg.h>

// 求2个数的最大公约数，辗转相除法
int GCD(int lhs, int rhs)
{
return rhs % lhs ? GCD(rhs % lhs, lhs) : lhs;
}

// n个数的最大公约数
int NGCD(int n, ...)
{
va_list argPtr;
va_start(argPtr, n);
int gcd = va_arg(argPtr, int);

for(int i = 1; i < n; ++i)
gcd = GCD(gcd, va_arg(argPtr, int));
va_end(argPtr);
return gcd;
}

// n个数的积
int NProduct(int n, ...)
{
int pdt = 1;

va_list argPtr;
va_start(argPtr, n);
for(int i = 0; i < n; ++i)
pdt *= va_arg(argPtr, int);
va_end(argPtr);
return pdt;
}

// n个数的最小公倍数
#define NLCM(n, ...) NProduct(n, __VA_ARGS__) / NGCD(n, __VA_ARGS__)

int main()
{
printf("GCD of 3,6,9: %d\n", NGCD(3, 3, 6, 9));
printf("LCM of 3,6,9: %d\n", NLCM(3, 3, 6, 9));

return 0;
}

Answer 3

void main()
{
int result=0;
int num1,num2;
scanf("%d%d",&num1,&num2);
for(int i=min(num1,num2); i>0; i--)
{
if(num1%i==0&&num2%i==0)
{
result = i;
break;
}
}
if(result==0)
{
printf("没有公约数\n");
}
else
{
printf("最大公约数为%d",result);
}

}

Answer 4

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

Answer 5

int gongyueshu(int m,int n)
{
int temp,k;

if(m<n)
{
temp=m;
m=n;
n=temp;
}
while((k=m%n)!=0)
{
m=n;
n=k;
}
return n;
}