写在前面： 我是「扬帆向海」，这个昵称来源于我的名字以及女朋友的名字。我热爱技术、热爱开源、热爱编程。
技术是开源的、知识是共享的。
这博客是对自己学习的一点点总结及记录，如果您对 Java、算法 感兴趣，可以关注我的动态，我们一起学习。
用知识改变命运，让我们的家人过上更好的生活。
相关文章
这篇博客利用辗转相除法和循环法来求解最大公约数和最小公倍数，有完整的代码实现。
一、辗转相除法
辗转相除法是求两个自然数的最大公约数的一种方法，也叫欧几里德算法。
算法思想：
用较大的数除以较小的数，然后用除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数。
假如需要求 390 和 338两个正整数的最大公约数,用欧几里德算法，是这样进行的：
390 / 338 = 1 (余52)
338 / 52 = 6 (余26)
52 / 26 = 0
因此390和338的最大公约数为 26
示例代码
求最大公约数：
public class Test1 {
public static void main(String[] args) {
System.out.println("输入两个正整数:");
Scanner scanner = new Scanner(System.in);
int num1 = scanner.nextInt();
int num2 = scanner.nextInt();
// 交换两个元素的值
int temp = 0;
if (num1 < num2) {
temp = num1;
num1 = num2;
num2 = temp;
}
// 利用辗转法求最大公约数
while (num2 != 0) {
temp = num1 % num2;
num1 = num2;
num2 = temp;
}
// 最大公约数 max
int max = num1;
System.out.println("最大公约数为：" + max);
}
}
代码执行结果：
输入两个正整数:
390
338
最大公约数为：26
最小公倍数的求法是利用两个数的乘积除以最大公约数
求最小公倍数：
public class Test2 {
public static void main(String[] args) {
System.out.println("输入两个正整数:");
Scanner scanner = new Scanner(System.in);
int num1 = scanner.nextInt();
int num2 = scanner.nextInt();
int num3 = num1 * num2;
// 交换两个元素的值（也可以用位运算的异或操作）
int temp = 0;
if (num1 < num2) {
temp = num1;
num1 = num2;
num2 = temp;
}
// 利用辗转法求最大公约数
while (num2 != 0) {
temp = num1 % num2;
num1 = num2;
num2 = temp;
}
// 最大公约数
int max = num1;
// 最小公倍数等于 两个数的乘积除以最大公约数
int min = num3 / max;
System.out.println("最大公约数为：" + max);
System.out.println("最小公倍数：" + min);
}
}
代码执行结果：
输入两个正整数:
338
390
最大公约数为：26
最小公倍数：5070
二、循环法
用两个数分别除以1开始一直到较小的一个数之间的所有数字，找到能被两个数字都能除尽的最大的一个数，就是它们的最大公约数。
示例代码：
public class Test3 {
public static void main(String[] args) {
System.out.println("输入两个正整数:");
Scanner scanner = new Scanner(System.in);
int num1 = scanner.nextInt();
int num2 = scanner.nextInt();
// 最大公约数
int max = 0;
// 最小公倍数
int min = 0;
// 交换两个元素的值,把第一个数标记为较小的一个
if (num1 > num2) {
num2 ^= num1;
num1 ^= num2;
num2 ^= num1;
}
// 循环求最大公约数
for (int i = 1; i <= num1; i++) {
if (num1 % i == 0 & num2 % i == 0) {
max = i;
}
}
// 求最小公倍数
min = num1 * num2 / max;
System.out.println("最大公约数为: " + max + ", 最小公倍数为：" + min);
}
}
代码执行结果：
输入两个正整数:
338
390
最大公约数为: 26, 最小公倍数为：5070