详解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; }