最小公倍数

最小公倍数（Least Common Multiple, LCM）是两个或多个整数共有的最小的正整数倍数。

题目描述

给定两个正整数 $a,b$，求他们的最小公倍数（lcm）。这两个整数均在 int 范围内。

输入格式

两个整数 $a$ 和 $b$，用空格分隔。

输出格式

一个整数表示答案。

样例输入

6 15

样例输出

30

求解方法

暴力求解法

首先选取lcm为两个数中较大的那个数，依次递增，第一个能整除两个数的lcm即为所求结果。

#include<iostream>
using namespace std;
int main(){
  int m,n;
  cin>>m>>n;
  int lcm=m>n?m:n;
  while(lcm%m!=0||lcm%n!=0){
    lcm++;
  }
  cout<<lcm;
  return 0;
}

公式法

假设m和n的最大公约数是gcd，则二者的最小公倍数lcm=(m×n)÷gcd 。

#include<iostream>
using namespace std;
int gcd(int m,int n){
 int r=m%n;
 while(r!=0){
   m=n;
   n=r;
   r=m%n;
 }
 return n;
}
int main(){
 int m,n;
 cin>>m>>n;
 int g=gcd(m,n);
 cout<<m*n/g;
 return 0;
}

短除法

短除法也是最小公约数求法篇中的一种方法，gcd=2×2×2×2，lcm=2×2×2×2×1×3。

#include<iostream>
using namespace std;
int main(){
  int m,n,gcd=1;
  cin>>m>>n;
  for(int i=2;i<=m&&i<=n;i++){
    while(m%i==0&&n%i==0){
      m=m/i;
      n=n/i;
      gcd=gcd*i;
    }
  }
  cout<<gcd*m*n;
  return 0;
}