计算最大公约数（GCD）

2023-10-11 16:41| 来源: 网络整理| 查看: 265

Greatest Common Divisor(GCD) 欧几里得算法据说是最早的算法，用于计算最大公约数，也是数论的基础算法之一。

这种方法又被称之为辗转相除法。还有一种更相减损法，暂不分析。

具体做法： 1.用较小数除较大数， 2.再用出现的余数（第一余数）（变成这一轮的除数）去除除数（变成这一轮的被除数） 3.再用出现的余数（第二余数）（变成这一轮的除数）去除第一余数（变成这一轮的被除数） 4.如此反复 5.直到最后余数是0为止。

如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

在这里插入图片描述

代码实现 //迭代法（递推法）：欧几里得算法：计算分子分母的最大公约数 public long getGcd(long a, long b) { while (a % b != 0) { long temp = a % b; a = b; b = temp; } return b; } //或许你会看到这个版本的代码，效果相同 public long getGcd(long a, long b) { while ( b > 0) { long temp = a % b; a = b; b = temp; } return a; }

两个版本的代码是一个意思，只不过第二个比第一个多循环了一次，将 b 赋给 a 后输出 a 。

第一次的取余操作可以保证使大数对小数取余，使得满足要求。

【本文地址】

公司简介

联系我们