分析
最大公約數
最大公約數是指兩個或多個整數共有約數中，最大的一個約數，常用的方法是歐幾里得演算法，也叫輾轉相除法，
假如需要求 1997 和 615 兩個正整數的最大公約數,用歐幾里得演算法，是這樣進行的：
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此，最大公約數為1
以除數和余數反復做除法運算，當余數為 0 時，取當前算式除數為最大公約數，所以就得出了 1997 和 615 的最大公約數
最小公倍數
知道了最大公約數，那么求最小公倍數就迎刃而解了，因為有這樣一個公式：a,b的最小公倍數=a*b/(a和b的最大公約數)
代碼
最大公約數
#include <cstdio>
using namespace std;
// 使用輾轉相除法求最大公約數
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;
}
最小公倍數
#include <cstdio>
using namespace std;
// 使用輾轉相除法求最大公約數
int GCD(int a,int b){
if (b == 0) {
return a;
}else{
return GCD(b, a % b);
}
}
// 求最小公倍數
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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/452803.html
標籤：C++