要求两个正整数的最大公约数有两种方法，辗转相除法和更相减损法。
注：gcd(a,b)代表a和b的最大公约数。
辗转相除法的定义：对于两个正整数a和b，其中a>b，r为a除以b的余数，gcd(a,b) = gcd(b,r)；
原理：设a，b的最大公约数为u，a = u · t1; b = u · t2; (t1 , t2 为某个数，满足等式要求，是多少并不重要，一定存在，因为u为a,b的约数)，a = nb + r(n为满足等式的某一个数，是多少并不重要，一定存在，因为a>b)；ssdxd = u(t1 - n·t2)；说明u也是r的约数。
更相减损法的定义：对于两个正整数a和b，其中a>b，l = a - b，gcd(a,b) = gcd(b,l)；
原理：证明同上，将假设的值带入等式，即可证除l也带有最大公约数u。
Java实现：
辗转相除法：
注意，如果b > a，此算法的第一次循环会将a b交换。
int num1 = 81;int num2 = 27;//辗转相除法while(num2 != 0){int temp = num2;num2 = num1 % num2;num1 = temp;}System.out.println("最大公约数为：" + num1);更相减损法：
注意：这个算法一定要保证a>b，否则a - b为负数，会出现bug。
int num3 = 55;int num4 = 25;//更相减损法while(num3 != num4){int temp = num4;if(num4 > num3){ temp = num4; num4 = num3; num3 = temp; }num4 = num3 - num4;num3 = temp;}System.out.println("大公约数为：" + num3);优化：
问题：
辗转相除法，在数值大的时候，需要进行大数除法，性能较低。
更相减损法：需要进行较多的循环，极端情况，a=1000,b=1，则需要循环999次。
这里提出一种结合方法，至于如何提出来的，我也是看别人写的，欣赏一下别人的天才哈。
如果a，b都是偶数，则gcd(a,b) = 2 · gcd(a/2,b/2)如果a是奇数，b是偶数，则gcd(a,b) = 2 · gcd(a,b/2) 因为其中一个为奇数，那么公约数的因素一定都不包含2如果a是偶数，b是奇数，则gcd(a,b) = 2 · gcd(a/2,b)如果a是奇数，b是奇数，则gdc(a,b) = gcd(b,a-b) 奇数相减，一定会出现偶数 int tt1 = 120; int tt2 = 92; //辗转相除法和更相减损法的结合//辗转相除法，大数相除性能较低//更相减损法，循环运算次数过多int base = 1;while(tt1 != tt2){ //保证tt1 是较大的数if(tt1 < tt2){int temp = tt1;tt1 = tt2;tt2 = temp;} //双偶if(tt1 % 2 == 0 && tt2 % 2 == 0){tt1 = tt1>>1;tt2 = tt2>>1;base = base * 2; //奇偶}else if(tt1 % 2 == 0 && tt2 % 2 != 0){tt1 = tt1>>1; //偶奇}else if(tt1 % 2 != 0 && tt2 % 2 == 0){tt2 = tt2>>1; //双奇}else if(tt1 % 2 != 0 && tt2 % 2 != 0){int temp = tt2;tt2 = tt1 - tt2;tt1 = temp;}}System.out.println("最大公约数为：" + tt2 * base);