求最大公约数和最小公倍数---辗转相除法(欧几里得算法)
目录
一.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的最大公约数，辗转相除法的步骤如下：
- 用a除以b，得到余数r；
- 如果r等于0，那么b就是最大公约数；
- 如果r不等于0，那么用b除以r，得到余数r1；
- 如果r1等于0，那么r就是最大公约数；
- 如果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;
}