分析
最大公約數(shù)
最大公約數(shù)是指兩個(gè)或多個(gè)整數(shù)共有約數(shù)中，最大的一個(gè)約數(shù)而克。常用的方法是歐幾里得算法笛厦，也叫輾轉(zhuǎn)相除法。
假如需要求 1997 和 615 兩個(gè)正整數(shù)的最大公約數(shù),用歐幾里得算法蝶缀，是這樣進(jìn)行的：
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此，最大公約數(shù)為1
以除數(shù)和余數(shù)反復(fù)做除法運(yùn)算算灸，當(dāng)余數(shù)為 0 時(shí)扼劈，取當(dāng)前算式除數(shù)為最大公約數(shù)驻啤，所以就得出了 1997 和 615 的最大公約數(shù)
最小公倍數(shù)
知道了最大公約數(shù)菲驴，那么求最小公倍數(shù)就迎刃而解了，因?yàn)橛羞@樣一個(gè)公式：a,b的最小公倍數(shù)=a*b/(a和b的最大公約數(shù))
代碼
最大公約數(shù)
#include <cstdio>
using namespace std;
// 使用輾轉(zhuǎn)相除法求最大公約數(shù)
int GCD(int a,int b){
if (b == 0) {
return a;
}else{
return GCD(b, a % b);
}
}
int main(){
int a,b;
while (scanf("%d%d",&a,&b)!=EOF){
printf("%d\n",GCD(a,b));
}
return 0;
}
最小公倍數(shù)
#include <cstdio>
using namespace std;
// 使用輾轉(zhuǎn)相除法求最大公約數(shù)
int GCD(int a,int b){
if (b == 0) {
return a;
}else{
return GCD(b, a % b);
}
}
// 求最小公倍數(shù)
int LCD(int a,int b){
return a * b / GCD(a, b);
}
int main(){
int a,b;
while (scanf("%d%d",&a,&b)!=EOF){
printf("%d\n", LCD(a,b));
}
return 0;
}
