一、背景介绍
在数学中,最大公约数(Greatest Common Divisor, 简称GCD)和最小公倍数(Least Common Multiple, 简称LCM)是两个非常重要的概念。
最大公约数是指两个或多个整数共有约数中最大的一个,例如 8 和 12 的最大公约数是 4。
最小公倍数是指两个或多个整数公有的倍数中最小的一个,例如 4 和 6 的最小公倍数是 12。
获得最大公约数和最小公倍数有很多方法,本文将介绍用C++实现的方法。
二、辗转相除法
辗转相除法,又称欧几里得算法,是求最大公约数的经典方法。该算法基于如下性质:两个正整数a和b(a>b)的最大公约数等于a除以b的余数c和b之间的最大公约数。
代码实现如下:
int gcd(int a, int b) { if (a < b) //保证a大于b swap(a, b); if (b == 0) return a; return gcd(b, a % b); }
对于求最小公倍数,可以先使用辗转相除法求出最大公约数,然后套用以下公式:
最小公倍数 = a×b / 最大公约数
代码实现如下:
int lcm(int a, int b) { return a * b / gcd(a, b); }
三、更相减损术
更相减损术是另一种求最大公约数的方法。该算法基于如下性质:两个正整数a和b(a>b)的最大公约数等于a-b的差值c和较小数b之间的最大公约数。
代码实现如下:
int gcd(int a, int b) { if (a < b) swap(a, b); while (a - b != b) //循环终止条件为 a-b=b { int temp = a - b; a = max(b, temp); b = min(b, temp); } return b; }
但是,这种算法的效率远低于辗转相除法,因此不常用。
四、更优秀的实现
虽然辗转相除法已经很优秀了,但是还是可以进一步优化。
一种优化的方法是 Stein算法,结合了更相减损术和位移运算的思想。该算法在计算机上运行的效率比辗转相除法要高,因为位移运算比除法运算要快。
代码实现如下:
int gcd(int a, int b) { if (a == 0) return b; if (b == 0) return a; int shift; for (shift = 0; ((a | b) & 1) == 0; ++shift) { a >>= 1; b >>= 1; } while ((a & 1) == 0) a >>= 1; do { while ((b & 1) == 0) b >>= 1; if (a > b) swap(a, b); b -= a; } while (b != 0); return a << shift; }
对于求最小公倍数,也可以使用 Stein算法。代码实现如下:
int lcm(int a, int b) { return a / gcd(a, b) * b; }
五、总结
求最大公约数和最小公倍数是我们在编程中经常会碰到的问题,本文主要介绍了辗转相除法、更相减损术和 Stein算法三种方法,其中辗转相除法是应用最广泛的。
需要注意的是,在使用求最小公倍数公式时,由于乘法运算的结果可能超出 int 类型的范围,因此需要使用更高精度的数据类型,如 long long。
希望本文能够对读者有所帮助。