最大公约数和最小公倍数

时间:2021-08-01 00:29:32

求最小公倍数算法

最小公倍数=两整数的乘积÷最大公约数

求最大公约数算法

辗转相除法

有两整数a和b:
① a%b得余数c
② 若c=0,则b即为两数的最大公约数
③ 若c≠0,则a=b,b=c,再回去执行①

#include <iostream>
#include <cmath>
using namespace std;

const float EPS = 0.00001;
int bei(int a, int b);
int yue(int a, int b);


int main()
{
int a, b;
while (cin>>a>>b)
{
cout<<bei(a, b)<<endl;
}
}

int bei(int a, int b)
{
return a * b / yue(a, b);
}

int yue(int a, int b)
{
int n = a % b;
while (n)
{
a = b;
b = n;
n = a % b;
}

return b;
}