详解C语言求两个数的最大公约数及最小公倍数的方法
求两个正整数的最大公约数
思路：这是一个很基本的问题，最常见的就是两种方法，辗转相除法和辗转相减法。通式分别为f(x,y)=f(y,x%y),f(x,y)=f(y,x-y)(x>=y>0)。根据通式写出算法不难，这里就不给出了。这里给出《编程之美》上的算法，主要是为了减少迭代的次数。
对于x和y，如果y=k*y1,x=k*x1，那么f(x,y)=k*f(x1,y1)。另外，如果x=p*x1，假设p为素数，并且y%p!=0，那么f(x,y)=f(p*x1,y)=f(x1,y)。取p=2。
参考代码：
//函数功能:求最大公约数
//函数参数:x,y为两个数
//返回值:最大公约数
intgcd_solution1(intx,inty)
{
if(y==0)
returnx;
elseif(x<y)
returngcd_solution1(y,x);
else
{
if(x&1)//x是奇数
{
if(y&1)//y是奇数
returngcd_solution1(y,x-y);
else//y是偶数
returngcd_solution1(x,y>>1);
}
else//x是偶数
{
if(y&1)//y是奇数
returngcd_solution1(x>>1,y);
else//y是偶数
returngcd_solution1(x>>1,y>>1)<<1;
}
}
}
求最小公倍数：
最常用的是辗转相除法，有两整数a和b：
①a%b得余数c
②若c=0，则b即为两数的最大公约数
③若c≠0，则a=b，b=c，再回去执行①
下面非递归版本：
intgcd_solution2(intx,inty)
{
intresult=1;
while(y)
{
intt=x;
if(x&1)
{
if(y&1)
{
x=y;
y=t%y;
}
else
y>>=1;
}
else
{
if(y&1)
x>>=1;
else
{
x>>=1;
y>>=1;
result<<=1;
}
}
}
returnresult*x;
}