求最大公约数和最小公倍数---辗转相除法(欧几里得算法)

目录

一.GCD和LCM

1.最大公约数

2.最小公倍数

二.暴力求解

1.最大公约数

2.最小公倍数

三.辗转相除法

1.最大公约数

2.最小公倍数

---

一.GCD和LCM

1.最大公约数

最大公约数（Greatest Common Divisor，简称GCD）指的是两个或多个整数共有的约数中最大的一个数。例如，整数12和30的约数有1、2、3、6，但其中最大的约数是6，因此12和30的最大公约数是6。

最大公约数在数学中有着广泛的应用，例如可以用于简化分数、判断两个数是否互质、求解线性方程等。

特殊的gcd(0,n)为n,n为任意数

2.最小公倍数

最小公倍数（Least common multiple , 简称LCM）是两个或多个整数中最小的能够被这些整数整除的正整数。换句话说，最小公倍数是这些整数的公共倍数中最小的一个。

例如，整数 6 和 8 的公共倍数包括 24、48、72 等，其中 24 是最小的一个，因此它们的最小公倍数是 24。

最小公倍数在数学和计算中经常使用，例如在分数的约分和通分、整数的约数分解、最简分式的求解等方面。

无法求0和一个数的最小公倍数

最小公倍数(LCM)=num1*num2/最大公倍数(GCD)

二.暴力求解

1.最大公约数

思路:考虑特殊情况,当num1和num2一个为0,返回另一个的值.

两个数的最大公约数,一定不可能在(min(num1,num2),max(num1,num2)]之间因为两者之中较小者的最大约数为本身,所以我们选择从较小者开始遍历,当都可以整除(也就是求余等于0)的时候,说明找到了最大公约数.

    public static int gcd(int num1, int num2) {if(num1==0)return num2;if(num2==0)return num1;int min = num1 < num2 ? num1 : num2;for (; min >= 1; --min) {if (num1 % min == 0 && num2 % min == 0) {return min;}}return min;}

2.最小公倍数

思路:

两个数的最小公倍数,一定不可能在[0,max(num1,num2))之间因为两者之中较大者的最大倍数为本身,所以我们选择从较大者开始遍历,当都可以被整除(也就是求余等于0)的时候,说明找到了最小公倍数.

    public static int lcm(int num1, int num2) {int max = num1 > num2 ? num1 : num2;for (; max <= num1 * num2; ++max) {if (max%num1==0&&max%num2==0) {return max;}}return max;}

三.辗转相除法

辗转相除法，又称欧几里得算法或辗转相减法，是一种求最大公约数（Greatest Common Divisor，简称GCD）的算法。

假设要求两个正整数a和b的最大公约数，辗转相除法的步骤如下：

1. 用a除以b，得到余数r；
2. 如果r等于0，那么b就是最大公约数；
3. 如果r不等于0，那么用b除以r，得到余数r1；
4. 如果r1等于0，那么r就是最大公约数；
5. 如果r1不等于0，那么继续用r除以r1，得到余数r2，以此类推，直到余数为0为止。

举个例子，假设要求36和24的最大公约数，辗转相除法的步骤如下：

36 ÷ 24 = 1 ... 12

24 ÷ 12 = 2 ... 0

因此，36和24的最大公约数是12。

辗转相除法的时间复杂度为O(logn)，其中n为a和b中较大的那个数的位数。因此，辗转相除法是一种高效的求最大公约数的方法，被广泛应用于计算机科学和数学领域。

1.最大公约数

1.递归方法求解

    //递归求解public static int gcd(int num1, int num2) {if (num2 == 0)return num1;return gcd(num2, num1 % num2);}

2.迭代方法求解

    //迭代求解public static int gcd(int num1, int num2) {int c = num1 % num2;while (c != 0) {num1 = num2;num2 = c;c = num1 % num2;}return num2;}

2.最小公倍数

最小公倍数(LCM)=num1*num2/最大公倍数(GCD)

    public static int lcm(int num1, int num2) {int x = num1, y = num2;int c = num1 % num2;while (c != 0) {num1 = num2;num2 = c;c = num1 % num2;}return x * y / num2;}