[求助]用C语言写辗转相除法又名欧几里德算法
3.辗转相除法又名欧几里德算法(Euclidean algorithm),是求两个正整数m,n(m>n)的最大公约数的算法。描述如下:为什么余数里面一定就包含了两个正整数的最大公约数?
首先,假设m和n的最大公约数为q,那么m=aq,n=bq(m>n)
m=n*k+r,则r=m-nk=q(a-bk),所以余数里面一定就包含了两个正整数的最大公约数。
请你编程实现利用辗转相除法求两个正整数m,n(m>n)的最大公约数。
这是网上查到的代码,我就是想问问为啥有x,y还有m,n
#include <stdio.h>
int gcd(int x,int y);
//调用函数库的求公约数函数
void main()
{
int m,n,i;
//申明整型变量:m,n,i
printf("input m,n:\n");
//输入提示句
scanf("%d,%d",&m,&n);
//等待输入两个数字并用逗号隔开
i=gcd(m,n);
//运算求公约数函数并将结果赋值给i
printf("最大公约数%d\n",i);
//输出结果
}
int gcd(int x,int y)
//调用函数库中的求公约数函数
{
int t;
//申明整型变量t
if(x<y)
{
t=x;
x=y;
y=t;
}
//如果x<y,那么把大的值赋值给x,小的值赋值给y
while(x% y!=0)
{
t=y;
y=x%y;
x=t;
}
//当xduiy求余不等于0时,把x对y求余的余数赋值给y,把y赋值给x
return y;
//返回值为y
}