首页 > 代码库 > 算法笔记_042:求最小公倍数(Java)

算法笔记_042:求最小公倍数(Java)

目录

1 问题描述

2 解决方案

 


1 问题描述

何为最小公倍数?能同时被数字m和数字n整除的最小整数。例如,2460的最小公倍数等于120。下面请编写相关函数实现求取数字mn的最小公倍数。

 


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)