c语言编程,利用辗转相除法求公约数

c语言编程,利用辗转相除法求公约数

辗转相除法， 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。
其原理如下：
设两数为a、b(b第一步：令c=gcd(a,b），则设a=mc，b=nc
第二步：根据前提可知r =a-kb=mc-knc=(m-kn)c
第三步：根据第二步结果可知c也是r的因数
第四步：可以断定m-kn与n互质【否则，可设m-kn=xd，n=yd (d>1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公约数成为cd，而非c，与前面结论矛盾】
从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)。
证毕。
以上步骤的操作是建立在刚开始时r!=0的基础之上的。即m与n亦互质。
按照其规则，C语言实现如下：

int GCD(int a,int b)
{return b==0？a:GCD(b,a%b)；}

最大公约数,最小公倍数都有了,请查收
int MaxCommonDivisor(int x,int y)
{
int temp;
if(x {
temp=x;
x=y;
y=temp;
}
while(y)
{
temp=x%y;
x=y;
y=temp;
}
return x;
}
int MinCommonMultiple(int x,int y)
{
return x*y/MaxCommonDivisor(x,y);
}

是最大公约数吗？不是的话你可以改一下
#include
void main()
{ unsigned int m,n,m1,n1,a;
printf("Enter two zheng numbers:");
scanf("%d%d",&m,&n);
m1=m;n1=n;
a=m1%n1;
while(a!=0)
{ m1=n1;n1=a;a=m1%n1;}
printf("%d ",n1);
}