首页 > 代码库 > 算法笔记_042:求最小公倍数(Java)
算法笔记_042:求最小公倍数(Java)
目录
1 问题描述
2 解决方案
1 问题描述
何为最小公倍数?能同时被数字m和数字n整除的最小整数。例如,24和60的最小公倍数等于120。下面请编写相关函数实现求取数字m和n的最小公倍数。
2 解决方案
关于本文求解最小公倍数的思想,来自于《算法设计与分析基础》第三版上一段讲解,具体如下:
具体代码如下:
package com.liuzhen.chapter6; public class LeastCommonMultiple { //使用欧几里得算法求解数m和数n最大公约数 public int getGcd(int m,int n){ while(n > 0){ int temp = m % n; m = n; n = temp; } return m; } //求解数m和n和最小公倍数 public int getLcm(int m,int n){ int gcd = getGcd(m,n); int result = m*n / gcd; return result; } public static void main(String[] args){ LeastCommonMultiple test = new LeastCommonMultiple(); System.out.println("60和16的最大公约数:"+test.getGcd(60, 12)); System.out.println("60和16的最小公倍数:"+test.getLcm(60, 12)); } }
运行结果:
60和16的最大公约数:12
60和16的最小公倍数:60
算法笔记_042:求最小公倍数(Java)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。