求出两个整数的最大公约数，要尽量优化算法的性能。

暴力枚举法

  1. public static int getGreatestCommonDivisor(int a, int b){
  2.     int big = a>b ? a:b;
  3.     int small = a<b ? a:b;
  4.     if(big%small == 0){
  5.         return small;
  6.     }
  7.     for(int i= small/2; i>1; i--){
  8.         if(small%i==0 && big%i==0){
  9.             return i;
  10.         }
  11.     }
  12.     return 1;
  13. }

辗转相除法（欧几里得算法）

这条算法基于一个定理：两个正整数 a 和 b (a > b)，它们的最大公约数等于 a 除以 b 的余数 c 和 b 之间的最大公约数。例如 10 和 25，25 除以 10 商 2 余 5，那么 10 和 25 的最大公约数，等同于 10 和 5 的最大公约数。

  1. public static int getGreatestCommonDivisorV2(int a, int b){
  2.     int big = a>b ? a:b;
  3.     int small = a<b ? a:b;
  4.     if(big%small == 0){
  5.         return small;
  6.     }
  7.     return getGreatestCommonDivisorV2(big%small, small);
  8. }

image.png

更相减损术

更相减损术， 出自中国古代的《九章算术》，也是一种求最大公约数的算法。古希腊人很聪明，可是我们炎黄子孙也不差。

它的原理更加简单：两个正整数 a 和 b (a > b)，它们的最大公约数等于 a - b 的差值 c 和较小数 b 的最大公约数。例如 10 和 25，25 减 10 的差是 15，那么 10 和 25 的最大公约数，等同于 10 和 15 的最大公约数。

由此，我们同样可以通过递归来简化问题。首先，计算出 a 和 b 的差值 c（假设 a > b），把问题转化成求 b 和 c 的最大公约数；然后计算出 c 和 b 的差值 d（假设 c > b），把问题转化成求 b 和 d 的最大公约数；再计算出 b 和 d 的差值 e（假设 b > d），把问题转化成求d 和 e 的最大公约数……

以此类推，逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算，直到两个数可以相等为止，最大公约数就是最终相等的这两个数的值。

  1. public static int getGreatestCommonDivisorV3(int a, int b){
  2.     if(a == b){
  3.         return a;
  4.     }
  5.     int big = a>b ? a:b;
  6.     int small = a<b ? a:b;
  7.     return getGreatestCommonDivisorV3(big-small, small);
  8. }