问题1216--基础练习——循环11(求两个正整数的最小公倍数)

1216: 基础练习——循环11(求两个正整数的最小公倍数)

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

题目描述

输入两个正整数m、n,求m、n的最小公倍数。

输入

一行两个正整数m、n,两数用一个空格隔开。( 1 ≤ m ≤ 105 ,1 ≤n ≤ 105 

输出

一行一个整数,表示m和n的最小公倍数

样例输入 Copy

12 18

样例输出 Copy

36

提示

一种方法就是使用穷举法,即使用循环从两个数中最大那个开始,逐个增加,不停测试是否能够同时被这两个数整除,如果可以,就找到了这两个数的最小公倍数,中断循环(break)。


另一种较好的方法
假设两个正整数 a、b 的最大公约数是 c ,最小公倍数是 d,则有 a*b = c*d 。这样就可以使用辗转相除法快速求得a、b的最大公约数c,这样就有a、b的最小公倍数 d = a*b/c
注意:对某些语言,如果a*b超出整数范围,可以先计算b/c,即 d= a*(b/c)。




来源/分类