基于C++求两个数的最大公约数最小公倍数

时间:2022-10-26 00:35:50

 x,y最大公约数的函数如下

int gys(int x,int y)
{ int temp;
while(x)
{temp=x;
x=y%x;
y=temp;}
return y;
}

       x=y的时候一目了然下面就不考虑,仅针对x不等于y的情况.在程序执行的某次循环过程中,若x>y,那这次循环仅换成了x和y数值的交换。这一点很关键。假设x,y的最大公约数为m。我们想办法来表示两者:那么有三种情况(i,j均为大于等于0的整数)

            1)x=m*(2i+1)   y=m*(2i+1)(此种情况i不等于j)
            2)x=m*(2i+1)   y=m*2j
            3)x=m*2i       y=m*(2j+1)

    发生有效循环时(这里的有效循环定义为除x,y交换数值循环外的循环,即x和y的数值至少有一个发生改变)。

    (1)若是第一种表示,因为执行x=y%x时x<y(即i<j)(注意若输入的x>y,则发生有效循环时已经完成交换),那么这次循环执行完的时候 x=m*2(j-i),y=m*(2i+1),即此时可以认为x=m*偶数,y=m*奇数,那么由于(偶数-奇数=奇数)且(奇数-偶数=奇数),那么每执行一次有效循环(注意执行有效循环时,一定是y>x),执行x=y%x实际做的是x=m*(若干次奇数减偶数或者偶数减奇数的的混合),注意此时的x=m*1才会满足使x=y%x=0进而使循环终止,执行此次循环的y可以是y=m*偶数或者y=m*奇数,由于x执行前赋值给temp,故最后返回的为y=temp=m,就是最大公约数。

    (2)第二种表示和第三种表示求公约数时实际上完全同第一种表示,因为只要是x,y为正整数且最大公约数为m,那么只要m*(2i+1),m*(2j+1),m*2(j-i)(或m*2(i-j))都大于0(此种情况i不等于j),最大公约数也是m。
     例如若能表示成x=m*(2i+1)   y=m*2j,他们的最大公约数和x=m*(2i+1)   y=m*(2(i+j)+1)是一样的,这可以写成第一种表示方法嘛,第三种表示也是一目了然的依次类推。

         这种方法也可以用来求x,y的最小公倍数,众所周知,最小公倍数==x*y/最大公约数


 简而言之。利用欧几里得辗转相除法。gcd(a,b)=gcd(b,a%b);