最小公倍数与最大公约数（三种算法）
倍数、约数：
整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。
最小公倍数：
两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。
最大公约数：
两个或多个整数共有约数中最大的一个。
求最大公约数：
一、穷举法：
整数a和b：
① i= a(或b)
② 若a、b能同时被i整除，则i即为最大公约数，return i ;
③ i–，再回去执行②
代码实现
#include <iostream> using namespace std; int main(){ int a,b; cin>>a>>b; for(int i=a;i>0;i--){ if(a%i==0&&b%i==0){ cout<<a<<"和"<<b<<"的最大公因数是"<<i<<endl; break; } } return 0; }
二、辗转相除法：
整数a和b：
① a%b得余数c
② 若c=0，则b即为两数的最大公约数
③ 若c≠0，则a=b，b=c，再回去执行①
例如：
求42和15的最大公约数过程为：
42÷15 余12
15÷12余3
12÷3余0
因此 3 即为最大公约数。
代码实现
#include <iostream> using namespace std; int main(){ int a,b; cin>>a>>b; int A,B; A=a;B=b; int c=a%b; while(c!=0){ a=b;b=c;c=a%b; } if(c==0) cout<<A<<"和"<<B<<"的最大公因数是"<<b<<endl; return 0; }
三、相减法
整数a和b：
① 若a>b，则a=a-b
② 若a<b，则b=b-a
③ 若a=b，则a（或b）即为两数的最大公约数
④ 若a≠b，则再回去执行①②
例如求27和15的最大公约数过程为：
a值
27－15＝12
( 15>12 )
b值
15－12＝3
( 12>3 )
a值
12－3＝9
( 9>3 )
a值
9－3＝6
( 6>3 )
a值
6－3＝3
( 3==3 )
因此，3即为最大公约数
代码实现
#include <iostream> using namespace std; int main(){ int a,b; cin>>a>>b; int A,B; A=a;B=b; while(a!=b){ if(a>b) a=a-b; else b=b-a; } if(a==b) cout<<A<<"和"<<B<<"的最大公因数是"<<b<<endl; return 0; }
求最小公倍数：
当我们利用上述算法求出来两个数的最大公约数后
最小公倍数=两整数的乘积÷最大公约数
