开发者社区> 谙忆> 正文

辗转相除法_欧几里得算法_java的实现(求最大公约数)

简介: 辗转相除法,又被称为欧几里德(Euclidean)算法, 是求最大公约数的算法。 当然也可以求最小公倍数。 算法描述   两个数a,b的最大公约数记为GCD(a,b)。a,b的最大公约数是两个数的公共素因子的乘积。
+关注继续查看

辗转相除法,又被称为欧几里德(Euclidean)算法, 是求最大公约数的算法。
当然也可以求最小公倍数。

算法描述

  两个数a,b的最大公约数记为GCD(a,b)。a,b的最大公约数是两个数的公共素因子的乘积。如462可以分解成2 × 3 × 7 × 11;1071可以分解成3 × 3 × 7 × 17。462和1071的最大公约数等于它们共有的素因数的乘积3 × 7 = 21。如果两数没有公共的素因数,那么它们的最大公约数是1,也即这两个数互素,即GCD(a,b)=1。另g=GCD(a,b),则a=mg, b=ng,其中m,n均为正整数。由上述分析可知,m,n互素。因为m,n没有公共素因子,GCD(m,n)=1。
  辗转相除法是一种递归算法。

算法实现:
递归版本:

    private static int gac(int a, int b) {
        if(a<b){
            swap(a,b);
        }
        if(b==0)
            return a;
        else
            return gcd(b,a%b);

    }

    private static void swap(int a, int b) {
        a=a^b;
        b=a^b;
        a=a^b;
    }

循环版本:

private static int gac(int a, int b) {
        if(a<b){
            swap(a,b);
        }
        while(b!=0){
            int c = a%b;
            a=b;
            b=c;
        }
        return a;
    }

    private static void swap(int a, int b) {
        a=a^b;
        b=a^b;
        a=a^b;
    }

2个数a,b;已知最大公约数为n;
最小公倍数=a*(b/n);

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Java 算法竞赛(蓝桥杯)常用API
Java 算法竞赛(蓝桥杯)常用API
94 0
归并排序 (分而治之算法) java代码实现(java完整代码)java递归实现(分而治之)MergeSort(分治法)
归并排序 (分而治之算法) java代码实现(java完整代码)java递归实现(分而治之)MergeSort(分治法)
18 0
如何优化大规模推荐?下一代算法技术JTM来了 | 开发者必读(077期)
最炫的技术新知、最热门的大咖公开课、最有趣的开发者活动、最实用的工具干货,就在《开发者必读》!
423 0
面试 | Java 算法的 ACM 模式
经常在 LeetCode 上用核心代码模式刷题的小伙伴突然用 ACM 模式可能会适应不过来,把时间花在输入输出上很浪费时间,因此本篇笔记对 Java 算法的 ACM 模式做了个小总结;
78 0
【大创_社区划分】——PageRank算法的解析与Python实现
一、什么是pagerank PageRank的Page可是认为是网页,表示网页排名,也可以认为是Larry Page(google 产品经理),因为他是这个算法的发明者之一,还是google CEO(^_^)。
1230 0
辗转相除法求最大公约数,非goto
1 #include 2 using namespace std; 3 //不推荐用goto,当然用它更快 4 //辗转相除法求两数的最大公约数 5 int gcd(long int a,long int b){ 6 int x=a
689 0
AES加密算法的JAVA实现
最近公司需要,看了看AES对称加密算法,具体原理没有仔细研究还,先说说用法吧,由于能力有限,不足之处请大家多多指教,好了,不说废话了,直接上代码 /** * 加密 * * @param content 需要加密...
785 0
算法研究之最大公约数
公约数:假设有两个数a,b,所谓的公约数就是能把a,b整除的最大整数。 求最大公约数的方法有很多。 方法1:穷举法,即通过循环找到一个2个数都能整除的数 public class Divide { public int getMaxDivide(int a,int b){ i...
552 0
C++项目参考解答-求最大公约数
【项目-求最大公约数】(1)输入两个数,并求出其最大公约数 #include &lt;iostream&gt; using namespace std; //自定义函数的原型(即函数声明) int main() { int a,b,g; cin&gt;&gt;a&gt;&gt;b; g=gcd(a,b); cout&lt;&lt;"最大公约数是: "&lt;&lt;g; re
899 0
+关注
谙忆
GitHub: https://github.com/chenhaoxiang
1455
文章
40
问答
文章排行榜
最热
最新
相关电子书
更多
OceanBase 入门到实战教程
立即下载
阿里云图数据库GDB,加速开启“图智”未来.ppt
立即下载
实时数仓Hologres技术实战一本通2.0版(下)
立即下载