【数论】最大公约数和最小公倍数

最大公约数的求法有两种：辗转相除法 和 枚举法。

枚举法

#include<iostream>
using namespace std;
int main(){int a,b,max;cout<<"请输入两个整数:";cin>>a>>b;for(int i=1;i<=a&&i<=b;i++){if(a%i==0&&b%i==0){max = i;}}cout<<"最大公约数为："<<max; return 0;
}

辗转相除法

#include<iostream>
using namespace std;
int main()
{int a,b,x;cout<<"请输入两个整数:";cin>>a>>b;while((x=a%b)!=0){a = b;b = x;}cout<<"最大公约数为："<<b; return 0;
}

请输入两个整数:32 24
最大公约数为：8

最小公倍数

最小公倍数 = a*b/最大公约数，所以我们得到最大公约数也就可以计算出最小公倍数。

—<完>—