欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

求最大公约数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与最大公约数的比