最大公约数,最小公倍数

时间:2023-01-14 00:30:04

首先记录两种求最大公约数的方法如下

1.辗转相除法(欧几里得算法)

具体的数学证明可以自行百度,博主数学不好,觉得知道这几个点就够了

前提是a>=b,if a%b == 0 then gcd(a,b) == b

else if a = bn+r then gcd(a,b) = gcd(b,r)...,那我们的任务就是在程序中判断两个参数之间能够整除即可

int gcd(int a,int b){
int tmp;
if(a < b){//确保前提a>=b
tmp = a;
a = b;
b = tmp;
}
tmp = 1;
while(tmp != 0){
tmp = a % b;
if(tmp){
a = b;
b = tmp;
}
}
return b;
}
2.更相减损法

更相减损实际上是辗转相除思想的另一种实现,但是运算方法靠的是减法,因此它的效率特别是在两个参数

相差较大的时候,就会显得慢一些。

int gcd(int a,int b){
int t = 1,tmp;
while(true){
if(a%2 == 0 && b%2 == 0){
t *= 2;
a /= 2;
b /= 2;
}
if(a < b){//确保前提a>=b
tmp = a;
a = b;
b = tmp;
}
tmp = a - b;
if(tmp == b){
return b*t;
}else{
a = tmp;
}
}
}

相比之下如果求两个数的最小公倍数的话,也是要借助最大公约数的

lcd(a,b) = a*b/gcd(a,b);

这里就不再给出程序以及证明了。。。