【C++】GCD and LCM

我们来看到最大公因数(GCD)及最小公倍数(LCM)啦!

最大公因数顾名思义就是两数或多个数间共同有的因数。

例如，2、4、8，的GCD是2，或6、12，的GCD是6。

学习目标: GCD、LCM的概念及实务

学习难度: ☆☆☆

我们来看它是怎麽被实现出来吧!

Recursion with GCD

#include <iostream>

using namespace std;

int GCD(int num1,int num2)
{
	if(num2==0)
	{
	 return num1;
	} 
	
	return GCD(num2,num1%num2);
}

int main()
{
	cout<<GCD(6,3); //2数最大公因数
    
    cout<<GCD((6,3),3); //3数最大公因数
	
	return 0;
}

最小公倍数是两个数或多个数最小共同有的倍数。

例如，2、4、8，的LCM是8，或6、12，的LCM是12。

Recursion with LCM

#include <iostream>

using namespace std;

int GCD(int num1,int num2)
{
	if(num2==0)
	{
	 return num1;
	} 
	
	return GCD(num2,num1%num2);
}

int LCM(int num1,int num2) //2数最小公倍数
{
	return((num1*num2)/GCD(num1,num2));
}

int LCM2(int num1,int num2,int num3) //3数最小公倍数
{
	return((num1*num2)/GCD((num1,num2),num3));
}

int main()
{	
	cout<<LCM(6,3);
    
    cout<<LCM2(6,3,3);

	return 0;
}

参考资料:

https://dotblogs.com.tw/peterkyo/2014/05/22/145207