Java中四种求最大公约数的方法及代码案例 |21xrx.com

Java中四种求最大公约数的方法及代码案例

2023-06-15 19:53:56 深夜i -- --

Java 最大公约数代码案例

在Java中，有多种方法可以求解最大公约数（GCD）。在本文中，将介绍四种不同的方法，并提供相应的代码案例。

方法一：暴力枚举法

暴力枚举法是求解GCD的最简单方法之一。该方法的基本思路是从两个数中较小的一个开始，遍历每个小于等于其值的正整数，直到找到两个数都可以整除的最大正整数，即为最大公约数。

代码实现：

public static int GCDByEnum(int a, int b) {

int smaller = a < b ? a : b;

int gcd = 1;

for (int i = 2; i <= smaller; i++) {

if (a % i == 0 && b % i == 0)

gcd = i;

}

return gcd;

}

方法二：辗转相除法

辗转相除法，也称欧几里得算法，指的是用两个整数的除数和余数的递归关系，来求解它们的最大公约数。基本思路是：对于任意正整数a和b，假设a > b，则a和b的最大公约数等同于b和a%b的最大公约数。

代码实现：

public static int GCDByDivide(int a, int b) {

if (a % b == 0)

return b;

else {

return GCDByDivide(b, a % b);

}

方法三：更相减损法

更相减损法是一种古老的求解最大公约数的方法。它的基本思想是：对于任意正整数a和b，假设a > b，则a和b的最大公约数等同于a-b和b的最大公约数。

代码实现：

public static int GCDBySubtract(int a, int b) {

if (a == b)

return a;

else {

int bigger = a > b ? a : b;

int smaller = a < b ? a : b;

return GCDBySubtract(bigger - smaller, smaller);

}

方法四：位运算法

位运算法是一种高效的求解最大公约数的方法。它的基本思路是：对于任意正整数a和b，假设a > b，则a和b的最大公约数等同于2的k倍（k为非负整数）与a-b的最大公约数。

代码实现：

public static int GCDByBit(int a, int b) {

if (a == b)

return a;

else if ((a & 1) == 0 && (b & 1) == 0) {

return GCDByBit(a >> 1, b >> 1) << 1;

} else if ((a & 1) == 0 && (b & 1) != 0) {

return GCDByBit(a >> 1, b);

} else if ((a & 1) != 0 && (b & 1) == 0) {

return GCDByBit(a, b >> 1);

} else {

int bigger = a > b ? a : b;

int smaller = a < b ? a : b;

return GCDByBit(bigger - smaller, smaller);

}

本文介绍了Java中的四种求解最大公约数的方法，包括暴力枚举法、辗转相除法、更相减损法和位运算法，并提供了相应的代码案例。这些方法各有优劣，可以根据实际需求进行选择。

上一篇: idea打包java可执行jar包

下一篇: 如何在C语言中输出之间增加空格

评论区

()

相似文章