求两个正整数的最大公约数

对于x和y，如果x=k*x，y=k*y，那么f(y,x)=k*f(y1,x1)。
另外，如果x=p*x1，假设p是素数，并且y%p!=0(即y不能被p整除），那么f(x,y)=f(p*x1,y)=f(x1,y)。

注意到以上两点后，我们就可以对这两点算法进行改进。

最简单的方法：我们知道2是一个素数

1.若x,y都是偶数，f(x,y)=2*f(x/2,y/2)=2(x>>1,y>>1)

2.若x为偶数，y为奇数，f(x,y)=f(x/2,y)=f(x>>1,y)

3.若x为奇数，y为偶数，f(x,y)=f(x,y/2)=f(x,y>>1)

4.若x为奇数，y为奇数，f(x,y)=f(x,x-y),(x-y)之后是一个偶数，下一步一定会有除以2的操作

#include<stdio.h>

/*
int gcd(int m,int n)
{
	if(n!=0)
		return gcd(n,m%n);
	else
		return m;
}
*/

int gcd(int m,int n)
{
	if(n!=0)
	{
		if(m%2==0&&n%2==0)
			return 2*gcd(m>>1,n>>1);
		else if(m%2==0&&n%2==1)
			return gcd(m>>1,n);
		else if(m%2==1&&n%2==0)
			return gcd(m,n>>1);
		else if(m%2==1&&n%2==1)
		{
			if(m>=n)
				return gcd(n,m-n);
			else
				return gcd(n,m);
		}
	}
	else
		return m;
}

int main()
{
	int m,n,result;
	printf("Ente two numbers:");
	scanf("%d%d",&m,&n);
	result=gcd(m,n);
	printf("The result is: %d\n",result);
	return 1;
}