2025年如何求解最大公约数和最小公倍数

1 定义

最大公约数

greatest common divisor，简写为gcd；或highestcommon factor，简写为hcf

如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。

例：在2、4、6中，2就是2，4，6的最大公约数。

最小公倍数

最小公倍数（Least Common Multiple，缩写L.C.M.）

最小公倍数=两数的乘积/最大公约数

欧几里德算法（辗转相除法）

1. 欧几里德算法和扩展欧几里德算法
1). 欧几里德算法
欧几里德算法又称辗转相除法，用于计算两个整数a, b的最大公约数。其计算原理依赖于下面的定理：
定理： gcd(a, b) = gcd(b, a mod b)

证明：
a可以表示成a = kb + r, 则r = a mod b
假设d是a, b的一个公约数，则有 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) 和(a, a mod b)的公约数是一样的，其最大公约数也必然相等，得证。

//------------------------------------------- //算法1：欧几里德算法（辗转相除法），求最大公约数，时间复杂度O(logn) //递归算法 public long long gcd(long long x, long long y) { if( y==0) //base case return x; else return gcd(y, x%y); } //end gcd() //非递归算法 public long gcd(int x,int y) { int temp; while(y!=0) { //base case : temp=x%y; x=y; y=temp; } //end while return x; } //end gcd() //------------------------------------------------------------------- //最小公倍数=两数的乘积/最大公约数，所以可在最大公约数的基础上求最小公倍数 public long lcm(int x,int y){ long gcd=gcd(x,y); return (x*y)/gcd; }//end lcm() //-------------------------------------------

2. Stein算法
欧几里德算法是计算两个数最大公约数的传统算法，无论是理论，还是从效率上都是很好的。但是他有一个致命的缺陷，这个缺陷只有在很大的素数时才会显现出来。
考虑现在的硬件平台，一般整数最多也就是64位，对于这样的整数，计算两个数值就的模很简单的。对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，而计算64位以下的整数模，也不过几个周期而已。但是对于更大的素数，这样的计算过程就不得不由用户来设计，为了计算两个超过64位的整数的模，用户也许不得不采用类似于多位除法手算过程中的试商法，这个过程不但复杂，而且消耗了很多CPU时间。对于现代密码算法，要求计算128位以上的素数的情况比比皆是，设计这样的程序迫切希望能够抛弃除法和取模。
Stein算法由J.Stein 1961年提出，这个方法也是计算两个数的最大公约数。和欧几里德算法不同的是，Stein算法只有整数的移位和加减法，这对于程序设计者是一个福音。
为了说明Stein算法的正确性，首先必须注意到以下结论：
gcd(a, a) = a，也就是一个数和他自己的公约数是其自身。
gcd(ka, kb) = k * gcd(a, b)，也就是最大公约数运算和倍乘运算可以交换，特殊的，当k=2时，说明两个偶数的最大公约数比如能被2整除。
Stein算法的python实现如下：

def gcd_Stein(a, b): if a < b: a, b = b, a if (0 == b): return a if a % 2 == 0 and b % 2 == 0: return 2 * gcd_Stein(a/2, b/2) if a % 2 == 0: return gcd_Stein(a / 2, b) if b % 2 == 0: return gcd_Stein(a, b / 2) return gcd_Stein((a + b) / 2, (a - b) / 2)

算法2

算法2：按照定义求解最大公约数和最小公倍数，从i=1每次加1到x和y中的较小的那个值，然后求能同时整除x和y的i值，这个过程是上图中的过程

最大公约数JAVA代码

public long gcd(int x,int y){ //获取两数较小值 if(x>y){ int temp=x; x=y; y=temp; }//end if int result=1; //最大公约数结果 for(int i=2;i<=x;i++){ if( (x%i==0) && (y%i==0) ){ result*=i; x=x/i; y=y/i; }//end if }//end for return result; }//end gcd()

最小公倍数：最小公倍数为最大公约数乘以最后的x和y值（），上述图中过程

public long lcm(int x,int y){ //获取两数较小值 if(x>y){ int temp=x; x=y; y=temp; }//end if int result=1; for(int i=2;i<=x;i++){ if( (x%i==0) && (y%i==0) ){ result*=i; x=x/i; y=y/i; }//end if }//end for return result=result*(x*y); }//end lcm()

【Google 2012校招笔试】求最大公约数
以下程序是用来计算两个非负数之间的最大公约数：
long long gcd(long long x, long long y) {
if( y==0) return 0;
else return gcd (y, x%y);
}
我们假设x,y中最大的那个数的长度为n，基本运算时间复杂度为O(1)，那么该程序的时间复杂度为：
A.O(1) B.O(logn) C.O(n) D.O(n^2)

【分析】选B.求最大公约数用的是辗转相除法（欧几里得算法），所以是O(logn)。

参考文献:

http://www.cnitblog.com/donne/archive/2008/07/23/47050.html

2025年如何求解最大公约数和最小公倍数

1 定义

欧几里德算法（辗转相除法）

算法2

相关推荐