欧几里得算法求最大公约数+最小公倍数

时间:2022-12-22 00:30:23

1,两个数互质:如果说两个数的公因数只有1,则可以说这两个数互质。

 

欧几里得算法求最大公约数:

首先求最大公约数,假设我们要求ab的最大公约数

a mod b = c

可以得到一下的递推过程:

a = kb + c ;

假设a , b 的最大公约数为d,则可以得到:

a = md , b = nd;

可知m , n 互质;

c = a - kb = md - knd = (m-kn)d;

我们已经知道m,n互质,则可以知道nm-kn互质,则cb的最大公约数也是d;

 

所以由以上的推论,我们可以得到,, b的最大公约数等于ba mod b 的最大公约数,递归迭代运算,直到两个数相等的时候,此时的ab的值即为最大公约数。

 

int             -2147483648 ~ +2147483647   (4 Bytes)
unsigned int         0 ~ 4294967295    (4 Bytes)
long == int
long long         -9223372036854775808 ~ +9223372036854775807    (8 Bytes)

 

 

欧几里得算法求最大公约数的局限性:

在应用辗转相除法求最大公约数的时候,如果利用上面的方法求最大公约数,如果要对大整数求最大公约数,辗转相除法的效率就出现了一定的问题,实际上对于大整数来说,大整数相除的时间开销是非常昂贵的,这就是辗转相除法的局限性。

 

解决方法:

可以借鉴欧几里得的辗转相除法,既然是取模运算导致的问题,那么我们就不用取模运算,换用“-”运算,即 f(x,y)=f(x-y,y);深入考虑一下发现在算法运行的过程可能会出现x<y的情况,这时候要交换x和y,但是结果不受影响。再来看看代码吧。

 

BigInt GCD(BigInt x,BigInt y)

{

  if(x < y) return GCD(y,x);

  return (!y) ? x : GCD(x-y,y);

}

代码中用到的BigInt是大整数类,可以存储成百上千位的整数。这个类怎么实现呢?这里不多说,具体网上有好多的相关文章来讲解高精度算法的,要是看书籍的话,强烈推荐ACM大牛刘汝佳的《算法竞赛入门经典》一书,对高精度的介绍还是非常好的。

对于大数运算问题是解决了,然而,细心的读者会发现,这个算法引入了另外一个问题,那就是当x和y相差很多时,算法的迭代次数会过高,导致了算法的效率较低,例如计算GCD(100000000000001,1)。这种情况确实存在啊,于是我们要考虑其他的优化了。

 

两个数的最小公倍数=两个数的乘机/最大公约数;