C语言求两个数m、n的最大公约数。（带注释）

2024-12-04 09:40:23

推荐回答（2个）

回答（1）：

<1>
用辗转相除法(欧几里德法)求最大公约数
算法描述:
m用n求余为a,
若a不等于0
则
m
=
n,
n
=
a,
继续求余
否则(即若a为0)
n
为最大公约数
gcd(int
a,
int
b)
{
int
t;
if
(a
<
b)
t=a,a=b,b=t;
if
(b
==
0)
return
a;
else
t=
a%b;
while
(t!=
0)
{
a=b;
b=t;
t=a%b;
}
return
b;
}
main()
{
int
a,b;
printf("输入两个数字:");
scanf("%d%d",&a,&b);
printf("%d\n",gcd(a,b));
}

回答（2）：

不是
有
辗转相除
法
吗
可以参考
下面
的
程序
void
main()
{
int
m,n,a,b,i;
scanf("%d%d",&m,&n);
i=m//返回m,n中较小的值
do
{
if(m%i==0
&&
n%i==0)
{
a=i;
//求出最大公约数
break;
}
}while(i--);
b=m*n/a;
//求出最小公倍数
printf("%d,%d",a,b);
}