文章目录

蛮力法

可以使用短除法找到这两个自然数的所有公因子，然后将这些公因子相乘结果就是这两个数的最大公约数。例如：48和36的公因子有2、2和3，相乘得12，则48和36的最大公约数就是12，可验证。另外，根据数学关系，两个数的乘积再除以他们的最大公约数就是最小公倍数，例如48*36除以12得到144,则144就是他们的最小公倍数，可验证。

#include<iostream>
using namespace std;
//蛮力法
int function1(int m,int n){
	int factor=1;//所有公因子的乘积 
	//1是所有自然数的公因子，所以循环从2开始寻找两个数的公因子 
	for(int i=2;i<=m&&i<=n;i++){
		while(m%i==0&&n%i==0){
			factor*=i;
			m/=i;
			n/=i;
		} 
	}
	return factor;
} 
int main(){
	int a1,a2;
	cout<<"请输入两个自然数：";
    cin>>a1;
    cin>>a2;
    int n=function1(a1,a2);
    cout<<"两个数的最大公约数为："<<n<<endl;
    int m=a1*a2/n;
    cout<<"两个数的最小公倍数为："<<m<<endl;
	return 0;
}

辗转相除法

一种效率更高的算法是辗转相除法，又称为欧几里得算法，其核心思想是将两个数不断地辗转相除直到余数为0，即可得到最大公约数，最小公倍数求法同上。

#include<iostream>
using namespace std;
//辗转相除法
int function2(int m,int n){
	int r=m%n;
	//循环终止条件是余数为0 
	while(r!=0){
		//辗转相除 
		m=n;
		n=r;
		r=m%n;
	}
	return n;
} 
int main(){
	int a1,a2;
	cout<<"请输入两个自然数：";
    cin>>a1;
    cin>>a2;
    int n=function2(a1,a2);
    cout<<"两个数的最大公约数为："<<n<<endl;
    int m=a1*a2/n;
    cout<<"两个数的最小公倍数为："<<m<<endl;
	return 0;
}