[两个数]最大公约(因)数和最小公倍数

最大公约数和最小公倍数

概念

最大公约数（Greatest Common Divisor：GCD）指某几个整数共有约数中最大的一个
最小公倍数（least common multiple：LCM） 指某几个整数公有的倍数中最小的一个正整数

相互之间关系及证明

两个整数的最小公倍数与最大公约数之间有如下的关系：最小公倍数 = 两数之积 / 最大公约数

证明：

证法一：

设a,b两个整数，假设最大公约数为gcd，最小公倍数为lcm。

根据公约数的定义有k1,k2使得

a = k1 * gcd；b = k2 * gcd；—— ①

其中 k1,k2互质，即两数除1之外没有其他公约数（gcd(k1, k2) = 1）

假设有其他公约数，那么a,b的最大公约数就不是gcd了，而是gcd乘另外的这个公约数，与假设矛盾。

所以观察（1）式，要能同时被a,b整除的数必须有 k1,k2的乘积（gcd(k1, k2) = 1），而又要求最小所以有lcm = k1 * k2 * gcd = a * b / gcd;

证法二：

根据公倍数的定义有t1,t2使得

lcm = a * t1 ；lcm = b * t2 ；将①式代入则有

k1 * gcd * t1 = lcm = k2 * gcd * t2； —— ②

并且k1,k2互质，t1,t2互质(证明类似k1,k2.若不互质，则有公约数，那么lcm就不是最小公倍数，而是lcm/这个公约数)，所以

（由②可得k1/k2=t2/t1;相等有两种情况，一是k1=ct2,k2=ct1,c!=1;二是k1=ct2,k2=ct1,c=1;因为k1,k2互质，t1,t2互质就是说这两个分式都办法约掉 除1之外的其他数，那么相等只有一种情况）

k1 = t2, k2 = t1;

代入lcm = k1 * gcd * t1 = k1 * k2 * gcd = a * b / gcd ;

所以，最小公倍数 = 两数之积 / 最大公约数

多个数的最大公约数和最小公倍数：

链接：http://www.cnblogs.com/tenjl-exv/p/7994818.html

求法及证明

最大公约数求解

一：穷举法

遍历2到min（a,b）之间的整数，

求出所有能够被a,b都整除的数，然后取最大。

若未找到则最大公约数为1。

这种方法对于两个都是很大的数要浪费很多时间。

自然我们就要寻找两个数公约数的一些性质，然后利用这些性质来减少运算量。

c++代码如下：

二：欧几里德算法

又名辗转相除法，用于计算两个整数a,b的最大公约数。

其计算原理依赖于下面的定理：

(a,b)和(b,a mod b)的公约数是一样的

定理：gcd(a,b) = gcd(b,a mod b)

证明：设r = a mod b；

则a可以表示成a = kb + r；

其中mod就是求余，r为余数，k为商。

假设d是a,b的一个公约数，则a,b能被d整除表示为d|a, d|b，而r = a - kb，因此 d|r

因此d是(b,a mod b)的公约数

假设d是(b,a mod b)的公约数，则d | b , d |r ，但是a = kb +r

因此d也是(a,b)的公约数

因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证。

c++代码如下：

三：更相减损法

其实质也类似于辗转相除法

不过把mod换成是减，gcd(a,b) = gcd(b,a - b)

即(a,b)和(b,a - b)的公约数是一样的（证明类似）和gcd(a,a)=a。

其流程是，先判断a，b是否为偶数，若是则除以2（节省时间，可省略）

然后将大的减小的用来更新大的，一直不断更新相减。

直到大的和小的相等的时候停止，

这个值就是最大公约数。

如求（91 49）的最大公约数:

91 49

42 49

42 7

35 7

28 7

21 7

14 7

7 7

而7和7的最大公约数就是7,(7,7)=7

所以(91,49)=(42,7)=(7,7)=7。

利用gcd(a,b) = gcd(b,a - b)更新，

利用gcd(a,a)=a得最后的值。

c++代码如下：

四：Stein算法

通过对两个数的奇偶性判断对更相减损法做一些适当的扩展就能够得到Stein算法。

主要利用到的原理有

1.gcd(ka,kb) = k gcd(a,b)，当k=2时，我们就能够先计算gcd(a,b)然后将结果乘以2就得到gcd(ka,kb)。

2.gcd(2a,b)=gcd(a,b)。这个容易理解，如果一个数能约a，必然能约2a。

3.利用更相减损法的结论。

有了上述规律就可以给出Stein算法如下：

如果A=0，B是最大公约数，算法结束

如果B=0，A是最大公约数，算法结束

设置A₁= A、B₁=B、C₁= 1

循环判断递归

如果A_n和B_n都是偶数，则An₊₁=A_n/2，B_n+1=B_n/2，C_n+1=C_n*2 (注意，乘2只要把整数左移一位即可，除2只要把整数右移一位即可)

如果A_n是偶数，B_n不是偶数，则A_n+1=A_n/2，B_n+1=B_n，C_n+1=C_n

如果B_n是偶数，A_n不是偶数，则B_n+1=B_{n /2}，A_n+1=A_n，C_n+1=C_n

如果A_n和B_n都不是偶数，则A_n+1=|A_n-B_n|，B_n+1=min(A_n,B_n)，C_n+1=C_n（利用更相减损法）

算法背景：

欧几里德算法是计算两个数最大公约数的传统算法，

他无论从理论还是从效率上都是很好的。

但是它有一个致命的缺陷，这个缺陷只有在大素数时才会显现出来。

考虑现在的硬件平台，一般整数最多也就是64位，

对于这样的整数，计算两个数之间的模是很简单的。

对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，

而计算64位以下的整数模，也不过几个周期而已。

但是对于更大的素数，这样的计算过程就不得不由用户来设计，

为了计算两个超过64位的整数的模，用户也许不得不采用类似于多位数除法手算过程中的试商法，

这个过程不但复杂，而且消耗了很多CPU时间。

对于现代密码算法，要求计算128位以上的素数的情况比比皆是，设计这样的程序迫切希望能够抛弃除法和取模。

Stein算法由J. Stein 1961年提出，这个方法也是计算两个数的最大公约数。

和欧几里德算法 算法不同的是，Stein算法只有整数的移位和加减法，这对于程序设计者是一个福音。

C++代码如下：

最大公约数求解

一：穷举法

穷举法就是以较大数为起始数，每次加一后判断是不是能整除要比较的这两个数，

如果能整除则退出循环，此数即为最小公倍数。

如果两数很大而又相差很小时，花费的时间时巨大的。

c++代码如下：

二：大数翻倍法

此算法是基于穷举法而加以改进的

还是以较大数为起始数，每次不是加一，而是翻倍（即乘2，乘3，乘4,,,,,,）

原因在于最小公倍数必整除此两个数，那么，每次判断时让较大数按倍数增长即可

c++代码如下：

三：利用最大公约数法

此方法直接利用最大公约数与最小公倍数的关系，

在已知最大公约数或已求出最大公约数的情况下直接求解最小公倍数

c++代码如下：

原文链接: https://www.cnblogs.com/tenjl-exv/p/7993997.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍