经典算法（2）- 用欧几里得算法求两个整数的最大公约数(GCD)

求两个整数的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）。

 

 

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