最大公約數的歐幾裡德算法

歐幾裡德算法：gcd(a,b) == gcd(a,(b mod a)):其中b>=a，我們首先證明下這個：

令c=gcd(a,b)，則存在整數k1，k2使 k1*c=a、k2*c=b；

令r=b mod a，則存在k3使得k3*a+r=b，将上面的a、b分别代入可得到：r=(k2-k1*k3)*c，即r（b mod a）是a、b最大公約數c的倍數。相應的代碼為：

package com.daelly.algorithm.hcf;

public class Main {

	public static void main(String[] args) {
		System.out.println(gcd(6, 4));
		System.out.println(gcd(6, 12));
		
		System.out.println(lcm(10, 8));
	}

	/**
	 * 歐幾裡德算法：
	 * gcd(a, b) == gcd((b % a), a)
	 * @param a
	 * @param b
	 * @return
	 */
	public static int gcd(int a, int b) {
		if(a > b) {//交換
			a = a + b;
			b = a - b;//after this b become a
			a = a - b;
		}
		
		int r = 0;
		while (a != 0) {
			r = b % a;
			b = a;
			a = r;
		}
		return b;
	}
	
	/**
	 * 最小公倍數，基于最大公約數來求
	 * @param a
	 * @param b
	 * @return
	 */
	public static int lcm(int a, int b) {
		return (a * b) / gcd(a, b);
	}
}