华为OD机考题(HJ108 求最小公倍数)

 前言

经过前期的数据结构和算法学习，开始以OD机考题作为练习题，继续加强下熟练程度。

描述

正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小公倍数。

数据范围：1≤𝑎,𝑏≤100000 1≤a,b≤100000 

输入描述：

输入两个正整数A和B。

输出描述：

输出A和B的最小公倍数。

示例1

输入：

5 7

输出：

35

实现原理与步骤

最大公约数 (GCD) 的计算：

• 使用欧几里得算法计算两个数的最大公约数。
• 在 gcd 方法中，使用 while 循环不断交换 a 和 b，并将 b 赋值为 a % b，直到 b 为0。最后返回 a 作为最大公约数。

最大公倍数 (LCM) 的计算：

• 使用公式 LCM(a,b)=∣a×b∣​/GCD(a,b)计算两个数的最大公倍数。
• 在 lcm 方法中，先调用 gcd 方法计算两个数的最大公约数，然后用上述公式计算最大公倍数。

实现代码

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别int a = in.nextInt();int b = in.nextInt();if (a > b) {int temp = a;a = b;b = temp;}int res=lcm(a,b);System.out.println(res);}//最大公约数public static int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b;a = temp;}return a;}//最小公倍数public static int lcm(int a,int b){return a*b/gcd(a,b);}
}

1.QA: