HJ108 求最小公倍数（Java版本）

一、试题地址

求最小公倍数_牛客题霸_牛客网

二、试题描述

描述

对于给定的两个正整数 a,b，它们的最小公倍数 lcm⁡(a,b) 是指能同时被 a 和 b 整除的最小正整数。
求解 lcm⁡(a,b)。

输入描述：

在一行上输入两个整数 a,b(1≦a,b≦105)。

输出描述：

输出一个整数，表示 lcm⁡(a,b)。

示例1

输入：

5 7

输出：

35

示例2 

输入：

2 4

输出：

4

三、运行要求

简单  通过率：37.19%  时间限制：1秒  空间限制：32M 

四、解题思路

最小公倍数乘以最大公因数（也叫最大公约数）等于这两个数的乘积，所以只要我们求出最大公因数就可以得到最小公倍数。

五、参考代码

package xu.com.coder.test10;import java.util.Scanner;public class Exam108 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int a = sc.nextInt();int b = sc.nextInt();System.out.println(getLeastCommonMultiple(a,b));}public static int getLeastCommonMultiple(int a, int b) {return a * b / gcd(a, b);}//求最大公因数private static int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}}

说明：这个求最大公因数的递归算法不知道是哪个大聪明第一次发现的，真的不得不佩服点赞！