介绍了求最大公约数的几种方法，蛮力法，辗转相除法，更相减损术，位移+更相减损术，有兴趣的可以参考 漫画算法：辗转相除法是什么鬼？，下面给出了几种方法的java实现。
代码如下：
/* 求最大公约数
* 参考--漫画算法：辗转相除法是什么鬼？
* http://blog.jobbole.com/106315/
* eclipse 自动导入 ctrl+shift+o
*/
import java.util.Scanner;
public class GCD {
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
int a=s.nextInt();
int b=s.nextInt();
int result1=brute_gcd(a,b);
int result2=Euclidean_gcd(a,b);
int result3=Decrease_gcd(a, b);
int result4=Bit_shift_gcd(a, b);
System.out.println("枚举法得到的结果:"+result1);
System.out.println("辗转相除法得到的结果:"+result2);
System.out.println("更相减损得到的结果:"+result3);
System.out.println("位移法得到的结果:"+result4);
}
//暴力枚举的方法，试图寻找到一个合适的整数 i，看看这个整数能否被两个整型参数a和b同时整除。
//当a=10000，b=10001时效果不好
//这里的话为了方便使得a总是大于b，如果不是，再递归一次(b,a),下面的其他方法也是这样子
public static int brute_gcd(int a,int b){
if(a>=b){
if(a%b==0)return b;
int result = 1;
for(int i=2;i<=b/2;i++){
if( a%i==0 && b%i==0 ){
result=i;
}
}
return result;
}
else return brute_gcd(b,a);
}
//Euclidean algorithm 欧几里得算法,又叫辗转相除法
//两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。
//逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算，直到两个数可以整除，或者其中一个数减小到1为止。
//同样当两个整数较大时取模运算的性能比较低，所以用减法来代替，有了更相减损术
public static int Euclidean_gcd(int a,int b){
if(a>=b){
if(a%b==0)return b;
else return Euclidean_gcd(a%b,b);
}
else return Euclidean_gcd(b,a);
}
//更相减损术， 出自于中国古代的《九章算术》，也是一种求最大公约数的算法。
//原理更加简单：两个正整数a和b（a>b），它们的最大公约数等于a-b的差值c和较小数b的最大公约数。
//逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算，直到两个数可以相等为止，最大公约数就是最终相等的两个数。
//这种方法也是有问题的，当a,b相差很大时如10000,2，就要递归很多次，继续优化，在此基础上利用位移
public static int Decrease_gcd(int a,int b){
if(a==b){
return a;
}
else if(a>b){
return Euclidean_gcd(a-b,b);
}
else{
return Euclidean_gcd(b,a);
}
}
/*
移位运算的性能非常快。对于给定的正整数a和b，不难得到如下的结论。其中gcb(a,b)的意思是a,b的最大公约数函数：
当a和b均为偶数，gcb(a,b) = 2*gcb(a/2, b/2) = 2*gcb(a>>1, b>>1)
当a为偶数，b为奇数，gcb(a,b) = gcb(a/2, b) = gcb(a>>1, b)
当a为奇数，b为偶数，gcb(a,b) = gcb(a, b/2) = gcb(a, b>>1)
当a和b均为奇数，利用更相减损术运算一次，gcb(a,b) = gcb(b, a-b)， 此时a-b必然是偶数，又可以继续进行移位运算。
*/
public static int Bit_shift_gcd(int a,int b){
if(a==b)return a;
else if(a>b){
//if(!((a&1)==0)&&(!(b&0x1)==0)){}来判断是否为偶数，其实是不对的，
//判断偶数奇数就需要a&1==0(a为偶数)或者a&1==1(a为奇数)就可以了
if(((a&1)==0)&&((b&0x1)==0)){
return Bit_shift_gcd(a>>1,b>>1)<<1;
}
else if(((a&1)==0)&&((b&1)==1)){
return Bit_shift_gcd(a>>1,b);
}
else if(((a&1)==1)&&((b&1)==0)){
return Bit_shift_gcd(a,b>>1);
}
return Bit_shift_gcd(b,a-b);
}
else return Bit_shift_gcd(b,a);
}
}
