多种方法求解“最大公约数”和“最小公倍数”
【摘要】 目录一、最大公约数1、枚举法2、辗转相除法二、最小公倍数1、枚举法2、扩大法Hello，大家好，我是灰小猿，一个超会写bug的程序猿。今天在这里记录一下在程序中求解两个数的最大公约数和最小公倍数的几种方法。一、最大公约数1、枚举法采用枚举法求解两个数的最大公约数是我们最常使用到的方法，两个整数的最大公约数为a，则a应该是大于等于1，小于等于这两个数的最小数的。因此我们可以在该范围内对可能...
目录
Hello，大家好，我是灰小猿，一个超会写bug的程序猿。
今天在这里记录一下在程序中求解两个数的最大公约数和最小公倍数的几种方法。
一、最大公约数
1、枚举法
采用枚举法求解两个数的最大公约数是我们最常使用到的方法，两个整数的最大公约数为a，则a应该是大于等于1，小于等于这两个数的最小数的。因此我们可以在该范围内对可能的数进行枚举即可。
使用程序如下：
/**
* 枚举法
* 求两个数的最大公约数
* */
static public int gcd1(int a,int b) {
int ans = 1;
int min = Math.min(a, b);
for (int i = 1; i <= min; i++) {
if (a%i==0&&b%i==0) {
ans = i;
}
}
return ans;
}
2、辗转相除法
辗转相除法是在数学中求解两个数的最大公约数的方法，
思路是：
1、大数除以小数，如果余数是0，那么最大公约数就是这个小数。
2、否则继续使用小数对得到的余数求余，直到余数为0，则结果等于最后的那个除数
程序如下：
/**
* 辗转相除法
* 求两个数的最大公约数
* */
static public int gcd2(int a,int b) {
if (a%b==0) {
return b;
}
return gcd2(b, a%b);
}二、最小公倍数
1、枚举法
采用枚举法求解两个数的最小公倍数的方法：最小公倍数的最小可能是这两个数的最大数，因此我们利用for循环从该最大数开始递增，直到找到第一个可以将这两个数除尽的数即可。程序如下：
/**
* 枚举法
* 求两个数的最小公倍数
* */
static public int lcm1(int a,int b) {
int max = Math.max(a, b);
for (int i = max; i <= a*b; i++) {
if (i%a==0&&i%b==0) {
max = i;
break;
}
}
return max;
}2、扩大法
扩大法其实也是枚举法的一种，只不过在for循环上效率高于第一种枚举法，我们在进行for循环时，是将较大数依次递增2倍、3倍...，直到找到第一个可以将这两个数除尽的数即可。程序如下：
/**
* 扩大法
* 求两个数的最小公倍数
* */
static public int lcm2(int a,int b) {
int max = Math.max(a, b);
for (int i = max; i <= a*b; i+=max) {
if (i%a==0&&i%b==0) {
max = i;
break;
}
}
return max;
}
关于求解最大公约数和最小公倍数的方法，之后还会继续更新效率更高的算法。
有问题的小伙伴也可以提出优化。
觉得不错记得点赞关注哟！
灰小猿陪你一起进步！
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）