牛客刷题——求最小公倍数

题目链接：求最小公倍数

题目描述

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

数据范围：1≤a,b≤100000
输入描述：
输入两个正整数A和B。

输出描述：
输出A和B的最小公倍数。

题目分析

最小公倍数指的是既能被A整除也能被B整数的最小的正整数。有如下几种解法：
1.暴力破解法
从两个数中较大的数开始，逐个向上进行判断，遇到的第一个能够被A和B整除的就是最小公倍数，但是这样时间复杂度会很高，需要不断进行判断。

2.更优解法
两个数的最小公倍数实际上就是两个数的乘积除以最小公约数。最小公约数可以使用辗转相除法进行求得。辗转相除法实现如下：

这里使用第二种方法来解决该问题，代码实现如下：

代码实现

#include<iostream>
using namespace std;


int gcd(int m,int n)
{
    
    int ret=0;
    while(ret=m%n)
    {
    
        m = n;
        n = ret;
    }
    return n;
}


int main()
{
    
    int a,b;
    cin>>a>>b;//赋值a，b
    int tmp = gcd(a ,b);//最小公约数
    int ret=(a*b)/tmp;//最小公倍数为两个数相乘除以最小公倍数
    cout<<ret<<endl;
    return 0;
}