网络推广方法有,怎样做网站性能优化,网站备案查询不了,移动端设计规范一、题目
输入描述#xff1a;
输入两个正整数A和B。
输出描述#xff1a;
输出A和B的最小公倍数。
示例1
输入#xff1a;
5 7
输出#xff1a;
35 示例2
输入#xff1a;
2 4输出#xff1a;
4二、思路解析
这道题#xff0c;也是模拟实现这一大类的一题…一、题目
输入描述
输入两个正整数A和B。
输出描述
输出A和B的最小公倍数。
示例1
输入
5 7
输出
35 示例2
输入
2 4输出
4二、思路解析
这道题也是模拟实现这一大类的一题。
在笔试面试一般是不会出现 最小公倍数 这么简单的题的出现的时候大都是作为一道编程题的其中一步。
那好回到题目上来希望各位看完我这篇博客能建立一个认知一看见最大公约数就要想起 “辗转相除法”。
我一年多以前也写过一篇辗转相除法的博客。
自认为讲得还算挺细的也是我阅读量最高的几篇博客之一想做这道题的朋友们建议都去看看
详解“辗转相除法”如何求最大公约数http://t.csdnimg.cn/Vsg8G
在这道题我们求的是最小公倍数那到底和最大公约数还有辗转相除法是什么关系呢
这里就要引出一条公式了 lcm(a, b) a * b / gcd(a, b) 其中lcm(a, b) 是求 a 和 b 的最小公倍数而 gcd(a, b) 则是求 a 和 b 的最大公约数。
因为最大公约数就是两个数的所有相同质数相乘的结果而最小公倍数就是扣除一次所有相同的质数。
想要求最小公约数的两个数 a 、b 相乘然后除以最大公约数一来一回刚好抵消结果就刚好是最小公倍数。 好那么 gcd(a, b) 又该如何求呢
gcd 不是最大公约数嘛那这时候就用到我们的 “辗转相除法了”所以就有了这条公式 gcd(a, b) gcd(b, a % b) 以上就是这道题的解题思路了具体实现请看下面代码 三、完整代码
import java.util.Scanner;public class Main {public static int gcd(int a, int b){if(b 0){return a;}return gcd(b, a % b);}public static void main(String[] args) {Scanner in new Scanner(System.in);int a in.nextInt();int b in.nextInt();System.out.println(a * b / gcd(a,b));}
} 以上就是本篇博客的全部内容啦如有不足之处还请各位指出期待能和各位一起进步
