/** * @author nonefly * 2015年8月27日 */public class Gcd {/**  * 暴力嘗試 */public static int gcd0(int a, int b) {if(a < 0 || b < 0)return -1;for (int i = a > b ? b : a; i > 1; i--) {if(a % i == 0 && b % i == 0)return i;}return 1;}/** 解法一  * 歐幾里得算法（輾轉相除法） * 求兩個數(a b,假設a > b)最大公約數, * 每次用較大數a除b取余, * 余數c不為0則讓較大數等于較小數，較小數等于余數,即: * a = b; b= c; */public static int gcd1(int a, int b) {if(a < 0 || b < 0)return -1;if(a == b || a == 0)return b;if(b == 0)return a;if(a < b)return gcd1(a, b % a);elsereturn gcd1(b, a % b);}/** * 更相減損術 來自《九章算術》 * ps:我也不知道這算法來頭，只是知道算法思想，查后才知它的出處和名字~ *  */public static int gcd2(int a, int b) {if(a < 0 || b < 0)return -1;if(a == b)return a;if((a & 1) > (b & 1))return gcd2(a, b >> 1);if((a & 1) < (b & 1))return gcd2(a >> 1, b);if((a & 1) == 0 && (b & 1) == 0)return gcd2(a >> 1, b >> 1) << 1;return gcd2(Math.abs(a - b), b > a ? a : b);}public static void main(String[] args) {System.out.PRintln(gcd0(99, 66));}}