网站制作公司咨询网站制作公司,电商建站价格,网站的技术解决方案,wordpress上传中文文件目录 一.GCD和LCM
1.最大公约数
2.最小公倍数
二.暴力求解
1.最大公约数
2.最小公倍数
三.辗转相除法
1.最大公约数
2.最小公倍数 一.GCD和LCM
1.最大公约数
最大公约数#xff08;Greatest Common Divisor#xff0c;简称GCD#xff09;指的是两个或多个整数共有…目录 一.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(num10)return num2;if(num20)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%num10max%num20) {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;}
