求最大公约数gcd(辗转相除法)
程序员文章站
2022-07-13 23:54:22
...
求最大公约数
求两个数的最大公约数可以用辗转相除法来实现,辗转相除法又叫欧几里得算法,辗转相除法的实现基于一个原理:
(a,b)=(a,ka+b),其中(a,b)表示a与b的最大公约数,a、b、k都为自然数
大概的意思就是两个数的最大公约数,其中一个数加到另一个数上得到的新数,与原数的公约数不变,代码如下,这里不需要比较m和n谁大,如果n>m,程序会自动交换m和n的值。当n为0时,返还的m就是最大公约数。
public static int gcd(int m,int n) {
int temp;
while(n != 0){
//辗转相除法
temp = m % n;
m = n;
n = temp;
}
return m;
}
内部过程:(48,30)=(30,18)=(18,12)=(12,6)=(6,0)=6
其实可以通过递归优化程序:
public static int gcd(int a,int b) {
if(a%b==0)
return b;
else
return gcd(b,a%b);//递归
}
内部过程:(48,30)=(30,18)=(18,12)=(12,6)=6
求最小公倍数
求最小公倍数只需要借助最大公约数来求,具体结论是:a和b的最小公倍数等于a乘b与最大公约数的比
上一篇: 求最大公约数(GCD)
下一篇: GCD求最大公约数