描述
对于给定的两个正整数 a,b，它们的最小公倍数 lcm(a,b) 是指能同时被 a 和 b 整除的最小正整数。
求解 lcm(a,b)。
求解 lcm(a,b)。
输入描述：
在一行上输入两个整数 a,b(1≦a,b≦105)。
输出描述：
输出一个整数，表示 lcm(a,b)。
解法一（java）：
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a = in.nextInt();
int b = in.nextInt();
int max = a > b ? a : b;
int p = a * b;
int result = p;
for (int i = max ; i <= p ; i++) {
if (i % a == 0 && i % b == 0) {
result = i;
break;
}
}
System.out.println(result);
}
}
思路：遍历，从两个数最大的那个数开始，然后一直遍历到两数相乘的结果，如果能满足条件就记录当前的值并退出循环，然后打印值即可。
解法二（java）：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int a = scanner.nextInt();
int b = scanner.nextInt();
System.out.println(lcm(a, b));
}
// 计算最大公约数 (GCD) 使用欧几里得算法
private static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// 计算最小公倍数 (LCM)
private static int lcm(int a, int b) {
return (a / gcd(a, b)) * b; // 先除后乘避免可能的整数溢出
}
}思路：
-
输入处理：使用
Scanner读取两个整数a和b。 -
GCD 计算：
gcd方法使用欧几里得算法递归地计算两个数的最大公约数。 -
LCM 计算：
lcm方法利用 GCD 的结果，通过公式(a × b) / GCD(a, b)计算最小公倍数。为了优化计算和避免整数溢出，先进行除法再进行乘法。 -
输出结果：打印计算得到的 LCM。
假如需要求 1997 和 615 两个正整数的最大公约数，用欧几里得算法，是这样进行的：
1997 ÷ 615 = 3 (余 152)
615 ÷ 152 = 4(余7)
152 ÷ 7 = 21(余5)
7 ÷ 5 = 1 (余2)
5 ÷ 2 = 2 (余1)
2 ÷ 1 = 2 (余0)
至此，最大公约数为1