题目的主要信息：

正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小公倍数。

方法一：

从第一个数字开始，逐渐递增，直到找到一个能同时整除a和b的数字，即为a和b的最小公倍数。

具体做法：

#include<iostream>
using namespace std;

int main(){
    int a, b;
    while(cin >> a >> b){
        int res = a;
        while((res%a)||(res%b)){//能同时整除a和b时就找到了最小公倍数
            res++;
        }
        cout<<res<<endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(ab-a)O(ab-a)$，从a开始遍历，最坏情况下最小公倍数为ab。
• 空间复杂度：$O(1)O(1)$,无额外空间。

方法二：

两个数a,b的最小公倍数是$a\ast b\mathrm{/}gcd(a,b)a*b/gcd(a,b)$，gcd(a,b)为最大公因子。因此我们可以用辗转相除法得到最大公因子，再计算最小公倍数。

具体做法：

#include <iostream>

using namespace std;

int gcd(int a, int b){//辗转相除法求最大公因子
    if(b==0){
        return a;
    }else{
        return gcd(b,a%b);//递归求解
    }
}

int process(int a, int b){//最小公倍数
    long f = gcd(a, b);//f为最大公因子
    return a*b/f; 
}

int main(){
    int a;
    int b;
    cin >> a >> b;
    cout<< process(a, b) <<endl;
    return 0;
}

复杂度分析：

• 时间复杂度：$O(loga)O(loga)$，gcd函数的时间复杂度为$O(loga)O(loga)$。
• 空间复杂度：$O(loga)O(loga)$，存在递归栈。