题目主要信息

1、手动输入两个正整数A和B

2、设计一个算法可以找出A和B的最小公倍数

3、最小公倍数是指能被A和B都能整除的最小正整数值

方法一：借助数学思维

具体做法

两个数的最小公倍数最小值一定是A和B中的最大值，最大值一定是AB，所以A和B的最小公倍数一定介于max(A,B)<= 最小公倍数<=AB。

Java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] s = bf.readLine().split(" ");
        int A = Integer.parseInt(s[0]);
        int B = Integer.parseInt(s[1]);

        // 求最小公倍数，最小公倍数一定大于等于最大的那个数
        int max = (A > B) ? A : B;
        // 定义一个中间变量，用于存储每次max加倍后的值
        int num = max;
        // 所以定义i为max的倍数，倍数i一定小于等于A和B中小的那个，因为最小公倍数最大为2个数乘积
        int n = Math.min(A,B);
        for (int i = 1; i <= n; i++) {
            //说明找到了最小公倍数 直接退出
            if (num % A == 0 && num % B == 0) {
                break;
            }
            //更新num的值
            else {
                num = max * i;
            }
        }
        //System.out.println(Math.max);
        System.out.println(num);
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$,因为这里只需要遍历A或者B的最小值即可。
• 空间复杂度：$O(1)O(1)$常数级别的临时变量。

方法二：借助最小公约数

具体做法

两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。整数a，b的最小公倍数记为$[a\mathrm{，}b][a，b]$，同样的，a，b，c的最小公倍数记为$[a\mathrm{，}b\mathrm{，}c][a，b，c]$，多个整数的最小公倍数也有同样的记号。

与最小公倍数相对应的概念是最大公约数，a，b的最大公约数记为$\mathrm{（}a\mathrm{，}b\mathrm{）}（a，b）$。关于最小公倍数与最大公约数，我们有这样的定理：$(a,b)\ast [a,b]=ab(a,b)*[a,b]=ab$(a,b均为整数)。

从定理中可以看到，如果要求两个数的最小公倍数，可以找到两个数的最大公约数，将两者的乘积除于两者的最大公约数，即可得到两者最小公倍数。

关于求两个数最大公约数，这里可以使用著名的欧几里得算法(欧几里得算法又称辗转相除法，是指用于计算两个非负整数]a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。)

Java代码

import java.util.Scanner;

public class Main {

    //gcd 模板
    static  int gcd(int m,int n)
    {   if(n == 0){
        return m;
    }
        int r = m%n;
        return gcd(n,r);
    }
    public static void main(String[] args) {
        //这里使用Scanner输入 和BufferedReader类似
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        System.out.println(A*B/gcd(A, B));
    }
}

复杂度分析

• 时间复杂度：$O(logn)O(logn)$,这里主要是求最大公约数的时间复杂度，其实也就是欧几里得算法的时间复杂度。
• 空间复杂度：$O(1)O(1)$常数级别的临时变量。