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

news/2024/12/29 6:00:31/

目录

一.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;}


http://www.ppmy.cn/news/32930.html

相关文章

C语言详解KMP算法

如果给你一个字符串 和 该字符串的一个子字符串 你能否快速找出该子字符串的所在位置我猜 这里会有一群杠精 说可以找到 真的吗 那下面这个字符串你可以一眼看出来吗你能找出来吗 如果能 算你眼神好 如果不能 那就看看接下来我怎么做你有想到暴力求解法吗&#xff1f;——来自百…

HTTPS,SSL(对称加密和非对称加密详解)

上一篇博客&#xff08;HTTP详解_徐憨憨&#xff01;的博客-CSDN博客&#xff09;详细讲解了关于HTTP的知识&#xff0c;了解到HTTP协议下的数据传输是一种明文传输&#xff0c;既然是明文传输&#xff0c;可能导致在传输过程中出现一些被篡改的情况&#xff0c;此时就需要对所…

Windows环境下实现设计模式——状态模式(JAVA版)

我是荔园微风&#xff0c;作为一名在IT界整整25年的老兵&#xff0c;今天总结一下Windows环境下如何编程实现状态模式&#xff08;设计模式&#xff09;。不知道大家有没有这样的感觉&#xff0c;看了一大堆编程和设计模式的书&#xff0c;却还是很难理解设计模式&#xff0c;无…

前端性能优化

总结 使用打包工具对代码进行打包压缩&#xff1b;引入css时采用link标签&#xff0c;并放入头部&#xff0c;使其与文档一起加载&#xff0c;减少页面卡顿时间&#xff1b;尽量减少dom结构的重排和重绘&#xff1b;使用css雪碧图&#xff0c;减少网络请求&#xff1b;对不同分…

C语言老题新解16-20 用命令行打印一些图案

文章目录11 打印字母C12 输出国际象棋棋盘。13 打印楼梯&#xff0c;同时在楼梯上方打印两个笑脸。14 输出9*9 口诀。15 有一道题要输出一个图形&#xff0c;然后Very Beautiful。11 打印字母C 11 用*号输出字母C的图案。 讲道理这绝对不该是个新人能整出来的活儿&#xff0c…

用sql计算两个经纬度坐标距离(米数互转)

目录 一、sql示例&#xff08;由近到远&#xff09; 二 、参数讲解 三、查询效果 - 距离&#xff08;公里 / 千米&#xff09; 四、查询效果 - 距离&#xff08;米&#xff09; 五、距离四舍五入保留后2位小数&#xff08;java&#xff09; 一、sql示例&#xff08;由近到远…

ElasticSearch快速入门详解(亲测好用,强烈推荐收藏)

3.快速入门 接下来快速看下elasticsearch的使用 3.1.概念 Elasticsearch虽然是一种NoSql库&#xff0c;但最终的目的是存储数据、检索数据。因此很多概念与MySQL类似的。 ES中的概念数据库概念说明索引库&#xff08;indices)数据库&#xff08;Database&#xff09;ES中可…

selenium(5)-------自动化测试脚本(python)

1)alert框的处理 前提:我们是不可以通过控制台直接定位元素的方式去选中这个alert框的&#xff0c;例如说xpath直接进行定位元素 1)先获得弹框的操作句柄:alertdriver.switch_to.alert 2)再次调用accept方法进行关闭弹窗:alert.accept() from selenium import webdriver import…