这篇文章主要介绍“怎么用Java求最大公约数”，在日常操作中，相信很多人在怎么用Java求最大公约数问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”怎么用Java求最大公约数”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！
计算
安全
数据库
网络和加速
企业服务
/**
* @date 2019/7/25 11:33
* description:求最大公约数
*/
public class CommonDivisor {
/**
* 第一版本
* 最简单的想法，找较小数的一半，从大到小，开始试着找出能够同时两个数整除最大数
* 这种方法暴力枚举，会循环很多次
*
* @param a
* @param b
* @return
*/
public static int getGreatestCommonDivisor(int a, int b) {
int big = a > b ? a : b;
int small = a < b ? a : b;
if (big % small == 0) {
return small;
}
for (int i = small / 2; i > 1; i--) {
if (small % i == 0 && big % i == 0) {
return i;
}
}
return 1;
}
/**
* 第二版本
* 欧几里得算法：辗转相除法求最大公约数
* 两个正数a和b(a>b),它们的最大公约数等于a和b相除的余数c和b的最大公约数 我们可以使用递归的方法简化问题
* eg 10和25 的最大公约数等于 余数5和10的最大公约数 5
* 缺点 ： 两个数较大时 a%b的转换效率低
*
* @param a
* @param b
* @return
*/
public static int getGreatestCommonDivisor2(int a, int b) {
int big = a > b ? a : b;
int small = a < b ? a : b;
if (big % small == 0) {
return small;
}
return getGreatestCommonDivisor2(big % small, small);
}
/**
* 第三版本
* 九章算术
* 更相减损术 :两个正整数a,b(a>b),他们的最大公约数等于a-b的差值c和较小数b的最大公约数
* 缺点：两数相差很大时，递归次数太大
*
* @param a
* @param b
* @return
*/
public static int getGreatestCommonDivisor3(int a, int b) {
if (a == b) {
return a;
}
int big = a > b ? a : b;
int small = a < b ? a : b;
return getGreatestCommonDivisor3(big - small, small);
}
/**
* 第四版本
* 九章算术 更相减损术和辗转相除法结合起来， 更相减损术上使用位移操作
* 更相减损术 :两个正整数a,b(a>b),他们的最大公约数等于a-b的差值c和较小数b的最大公约数
* 缺点：两数相差很大时，递归次数太大
*
* @param a
* @param b
* @return
*/
public static int getGreatestCommonDivisor4(int a, int b) {
if (a == b) {
return a;
}
if ((a & 1) == 0 && (b & 1) == 0) {
return getGreatestCommonDivisor4(a >> 1, b >> 1) << 1;
} else if ((a & 1) == 0 && (b & 1) != 0) {
return getGreatestCommonDivisor4(a >> 1, b);
} else if ((a & 1) != 0 && (b & 1) == 0) {
return getGreatestCommonDivisor4(a, b >> 1);
} else {
int big = a > b ? a : b;
int small = a < b ? a : b;
return getGreatestCommonDivisor4(big - small, small);
}
}
public static void main(String[] args) {
System.out.println(getGreatestCommonDivisor4(25, 5));
System.out.println(getGreatestCommonDivisor4(100, 80));
System.out.println(getGreatestCommonDivisor4(27, 14));
}
}到此，关于“怎么用Java求最大公约数”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://my.oschina.net/iioschina/blog/3079011
