Niu Ke's question -- finding the least common multiple

Topic link ： Find the least common multiple

Title Description

Positive integer A And positive integers B The least common multiple of is Can be A and B The smallest positive integer value of an integer division , Design an algorithm , Find input A and B The least common multiple of .

Data range ：1≤a,b≤100000
Input description ：
Enter two positive integers A and B.

Output description ：
Output A and B The least common multiple of .

Topic analysis

The least common multiple means that both can be A Divisibility can also be B The smallest positive integer of an integer . There are several solutions as follows ：
1. brute-force attack
Start with the larger of the two numbers , Judge one by one , The first one you encounter can be A and B Divisible is the least common multiple , But the time complexity will be very high , Constant judgment is required .

2. Better solution
The least common multiple of two numbers is actually the product of two numbers divided by the least common divisor . The least common divisor can be obtained by rolling division . The rolling phase division method is realized as follows ：

Here we use the second method to solve this problem , The code implementation is as follows ：

Code implementation

#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;// assignment a,b
    int tmp = gcd(a ,b);// The least common divisor 
    int ret=(a*b)/tmp;// The least common multiple is the multiplication and division of two numbers by the least common multiple 
    cout<<ret<<endl;
    return 0;
}