欧几里得算法(辗转相除法)

介绍

欧几里得算法,又称辗转相除法,用于计算两个整数的最大公约数。

原理

下面通过一个例子介绍其原理:计算105和24的最大公约数:

105 = 24 x 4 + 9 24 = 9 * 2 + 6 9 = 6 * 1 + 3 6 = 3 * 2 + 0

当余数为0时,可得到最大公约数。105和24的最大公约数是3.

代码实现

递归版本:

public static int gcd (int p, int q) {
    if (q == 0)     return p;
    else            return gcd (q, p%q);}

循环版本:

public static int gcdLoop (int p, int q) {
    while (q != 0) {
        int rem = p % q;
        p = q;
        q = rem;
    }
    return p;}

原文发布于微信公众号 - mwangblog(mwangblog)

原文发表时间:2018-07-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏進无尽的文章

RunTime 之Method Swizzling

有关Runtime的知识总结,我本来想集中写成一篇文章的,但是最后发现实在是太长,而且不利于阅读,最后分成了如下几篇:

13220
来自专栏Golang语言社区

Golang精编100题

能力模型 级别模型初级 primary熟悉基本语法,能够看懂代码的意图; 在他人指导下能够完成用户故事的开发,编写的代码符合CleanCode规范;中级 int...

435110
来自专栏SeanCheney的专栏

Python解答LeetCode

古有科举八股,今有LeetCode。 八股定格式而取文采心意,LeetCode定题目且重答案背诵。 美其名曰:"practice makes perfec...

796160
来自专栏Brian

Python进阶教程(一)

概述 hi,朋友们大家好,今天将英文原著作者 @yasoob《Intermediate Python》进行翻译和在工作中使用的Python技巧进行了总结。Git...

38970
来自专栏刘望舒

JNI的实现原理

JNI是Java Native Interface的缩写,它为java提供了调用C和C++代码的能力。java.lang包下的很多类都用到了native方法,比...

58720
来自专栏C语言及其他语言

【优秀题解】判断素数问题的题解与代码

题目描述 写一个判断素数的函数,在主函数输入一个整数,输出是否是素数的消息。 输入 一个数 输出 如果是素数输出prime 如果不是输出not prime 原题...

30360
来自专栏web前端教室

javascript 红皮高程(17)

按位操作符真是有头大的感觉,其实我也不太清楚哪里可以用到它。但即使不懂,也要先学会再说。 今天继续,按位或(OR), 它由一个竖线符号(|) 表示,同样也是操作...

200100
来自专栏菩提树下的杨过

common-pool2 学习:thrift连接池的另一种实现

对象池是一种很实用的技术,经典的例子就是数据库连接池。去年曾经从零开始写过一个thrift客户端连接池。如果不想重造轮子,可以直接在apache开源项目comm...

38080
来自专栏Pythonista

Python之路,Day2 - Python基础,列表,循环

11420
来自专栏CSDN技术头条

【问底】静行:FastJSON实现详解

还记得电影《功夫》中火云邪神的一句话:天下功夫,无坚不破,唯快不破。在程序员的世界中,“快”一直是大家苦苦修炼,竞相追逐的终极目标之一,甚至到了“不择手段”、“...

31370

扫码关注云+社区

领取腾讯云代金券