今天看了编程之美中的求解最大公约数问题，想着自己动手写一些程序实现
解法一：碾转相除法
求x,y的最大公约数，取k=x/y，b=x%y,则有 x=ky+b
如果一个整数能够同时整除x和y，则必能同时整除b和y
而能够同时整除b和y的数也必能同时整除x和y 那么就可以知道x和y的公约数与b和y的公约数是相同的，其最大公约数也是相同的。
则 有 f（x，y）=f(y，x%y) x>=y>0
如下示例：
f(42,30)=f(30,12)=f(12,6)=f(6,0)=6
代码如下：
<span style="font-size:18px;">#include<stdio.h>
int gcd(int x,int y);
void main()
{
int x,y;
scanf("%d%d",&x,&y);
printf("The GCD is :%d\n",gcd(x,y));
}
int gcd(int x,int y)
{
return (!y)?x:gcd(y,x%y);
}</span>
解法二： 不采用取模运算（对于大整数）
如果一个整数能够同时整除x和y 那么必能同时整除x-y和y
同理如果能够同时整除 x-y和y 那么也必能同时整除x和y
上面的x>=y，运算前可以先把大数放前面
如实例：
f（42，30）=f（30，12）=f（12，18）=f（18，12）=f（12，6）=f（6，6）=f（6，0）=6
代码如下：
#include<stdio.h>
int gcd(int x,int y);
void main()
{
int x,y;
scanf("%d%d",&x,&y);
printf("The GCD is :%d\n",gcd(x,y));
}
int gcd(int x,int y)
{
if(x<y)
return gcd(y,x);
if(y==0)
return x;
else
return gcd(x-y,y);
}
解法三: 综合解法一和解法二的优点
解法二迭代次数可能很多如一个大整数 和一个非常小的数
解法一在于大整数取模运算开销大
对于x和y来说 如果 y=k*y1 x=k*x1 那么有 f（x，y）=k*f（y1，x1）
另外，如果x=p*x1 假设p是素数，并且y%p!=0 那么f(x，y)=f（p*x1，y）=f（x1，y）
我们知道2是一个素数，所以利用上面的可以进行分析
取p=2；
如果x,y都为偶数 那么f（x，y）=2*f（x/2,y/2）=2*f(x>>1,y>>1);
如果x为偶数，y为奇数 那么 f（x，y）=f（x/2,y）=f(x>>1,y);
如果y为偶数，x为奇数 那么 f（x，y）=f（x,y/2）=f(x,y>>1);
如果x为奇数，y为奇数 那么 f（x，y）=f（y,x-y); x-y为偶数 那么也可以进行移位操作
代码如下：
#include<stdio.h>
int gcd(int x,int y);
void main()
{
int x,y;
scanf("%d%d",&x,&y);
printf("The GCD is :%d\n",gcd(x,y));
}
int gcd(int x,int y)
{
if(x<y)
return gcd(y,x);
if(y==0)
return x;
else
{
if(x%2==0)
{
if(y%2==0)
return (gcd(x >> 1,y >> 1)<<1);
else
return gcd(x >>1 ,y);
}
else
{
if(y%2==0)
return (gcd(x,y >> 1));
else
return (gcd(y,x-y));
}
}
}