学步园

求两个整数的GCD有两个方法：采用欧几里得算法(Euclid's Algorithm)和二进制GCD算法, 这里实现的是欧几里得算法。

欧几里得算法基本原理很简单，即:
 m = q1.n + r1
 m2= q2.n2 + r2

    ....

 mi = qi.ni + ri
其中m2=n, n2=r1....

gcd(m,n) = gcd(m2,n2) ＝ gcd(mi,ni)....直到ri=0（因为0<=ri<ni，所以ri可以收敛到0）。

/**<br /> *<br /> * @author ljs 2011-5-17<br /> *<br /> * solve gcd(m,n) using Euclid's Algorithm<br /> *<br /> */<br /> public class GCD_Euclid {<br /> //Euclid's Algorithm to solve gcd(greatest common divisor)<br /> public static int gcd(int m,int n){<br /> m = (m<0)?-m:m;<br /> n = (n<0)?-n:n;</p> <p> if(n==0)<br /> return m;<br /> /*<br /> //this swap is not needed, since: m % n=m when m<n; so the next recursion will change to gcd(n,m)<br /> if(m<n){<br /> int tmp = n;<br /> n=m;<br /> m=tmp;<br /> }<br /> */<br /> return gcd(n,m%n);<br /> }<br /> //an implementation without recursion<br /> public static int gcdNoTailRecursion(int m,int n){<br /> m = (m<0)?-m:m;<br /> n = (n<0)?-n:n;</p> <p> while(n!=0){<br /> int remainder = m%n;<br /> m = n;<br /> n = remainder;<br /> }<br /> return m;<br /> }<br /> public static void print(int m,int n,int gcd){<br /> m = (m<0)?-m:m;<br /> n = (n<0)?-n:n;<br /> System.out.format("gcd of %d and %d is: %d%n",m,n,gcd);<br /> }<br /> public static void main(String[] args) {<br /> int m = -18;<br /> int n= 12;<br /> print(m,n,gcd(m,n));<br /> print(m,n,gcdNoTailRecursion(m,n));</p> <p> //co-prime<br /> m = 15;<br /> n= 28;<br /> print(m,n,gcd(m,n));<br /> print(m,n,gcdNoTailRecursion(m,n));</p> <p> m = 6;<br /> n= 3;<br /> print(m,n,gcd(m,n));<br /> print(m,n,gcdNoTailRecursion(m,n));</p> <p> m = 6;<br /> n= 3;<br /> print(m,n,gcd(m,n));<br /> print(m,n,gcdNoTailRecursion(m,n));</p> <p> m = 6;<br /> n= 0;<br /> print(m,n,gcd(m,n));<br /> print(m,n,gcdNoTailRecursion(m,n));</p> <p> m = 0;<br /> n= 6;<br /> print(m,n,gcd(m,n));<br /> print(m,n,gcdNoTailRecursion(m,n));</p> <p> m = 0;<br /> n= 0;<br /> print(m,n,gcd(m,n));<br /> print(m,n,gcdNoTailRecursion(m,n));</p> <p> m = 1;<br /> n= 1;<br /> print(m,n,gcd(m,n));<br /> print(m,n,gcdNoTailRecursion(m,n));</p> <p> m = 3;<br /> n= 3;<br /> print(m,n,gcd(m,n));<br /> print(m,n,gcdNoTailRecursion(m,n));</p> <p> m = 2;<br /> n= 2;<br /> print(m,n,gcd(m,n));<br /> print(m,n,gcdNoTailRecursion(m,n));</p> <p> m = 1;<br /> n= 4;<br /> print(m,n,gcd(m,n));<br /> print(m,n,gcdNoTailRecursion(m,n));</p> <p> m = 4;<br /> n= 1;<br /> print(m,n,gcd(m,n));<br /> print(m,n,gcdNoTailRecursion(m,n));</p> <p> m = 10;<br /> n= 14;<br /> print(m,n,gcd(m,n));<br /> print(m,n,gcdNoTailRecursion(m,n));</p> <p> m = 14;<br /> n= 10;<br /> print(m,n,gcd(m,n));<br /> print(m,n,gcdNoTailRecursion(m,n));</p> <p> m = 10;<br /> n= 4;<br /> print(m,n,gcd(m,n));<br /> print(m,n,gcdNoTailRecursion(m,n));</p> <p> m = 273;<br /> n= 24;<br /> print(m,n,gcd(m,n));<br /> print(m,n,gcdNoTailRecursion(m,n));</p> <p> m = 120;<br /> n= 23;<br /> print(m,n,gcd(m,n));<br /> print(m,n,gcdNoTailRecursion(m,n));</p> <p> }<br /> }<br />