算法-最小公倍数

1.  方法一:穷举法
2.  方法二:公式lcm = a * b / gcd(a,b)

1. 穷举法

#include<iostream>
using namespace std;
unsigned long LCM(unsigned long a, unsigned long b)
{
	if(a * b == 0)
		return 0;
	unsigned long lcm = a > b ? a : b;
	while(1)
	{
		if((lcm%a==0) && (lcm%b==0))
			break;		
		lcm++;
	}
	return lcm;
}

void main()
{
	unsigned long a,b;
	cout<<"请输入a 和b:>";
	cin>>a>>b;

	unsigned long lcm = LCM(a,b);
	cout<<"lcm = "<<lcm<<endl;
}

公式lcm = a * b / gcd(a,b)     。依赖最大公约数GCD的方法

#include<iostream>
using namespace std;
unsigned long GCD(unsigned long a, unsigned long b)
{
	if(b == 0)
		return a;
	else
		return GCD(b, a%b);
}
unsigned long LCM(unsigned long a, unsigned long b)
{
	if(a * b == 0)
		return 0;
	return (a*b)/GCD(a,b);
}

void main()
{
	unsigned long a,b;
	cout<<"请输入a 和b:>";
	cin>>a>>b;

	unsigned long lcm = LCM(a,b);
	cout<<"lcm = "<<lcm<<endl;
}