求两个整数的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 ......
阅读全文