题意整理

  • 给定两个不大于100的正整数。
  • 求它们的最小公倍数。

方法一（循环）

1.解题思路

  • 首先计算m和n中的较大者，用max记录。
  • 然后利用循环，在max到m*n之间找最小公倍数。
  • 如果既能被m整除又能被n整除，说明是最小公倍数，直接返回。

动图展示： alt

2.代码实现

import java.util.*;

public class Main {
    public static void main(String[] args) {
        //标准输入
        Scanner console = new Scanner(System.in);
        int m = console.nextInt();
        int n = console.nextInt();
        //计算最小公倍数
        int result = getCM(m, n);
        //输出结果
        System.out.println(result);
    }

    //计算最小公倍数
    public static int getCM(int m, int n){
        //计算m、n中较大者
        int max=Math.max(m,n);
        //从max到m*n之间找最小公倍数
        for(int i=max;i<=m*n;i++){
            //如果既能被m整除又能被n整除，说明是最小公倍数，直接返回
            if(i%m==0&&i%n==0){
                return i;
            }
        }
        return -1;
    }
    
}

3.复杂度分析

  • 时间复杂度：最坏情况下，总共需要循环m∗n−max+1m*n-max+1次，所以时间复杂度为O(m∗n−max)O(m*n-max)。
  • 空间复杂度：需要额外常数级别的空间，所以空间复杂度为O(1)O(1)。