1.题目

求出两个整数的最大公约数

2.方法

(1)暴力枚举法

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

(2)辗转相除法
(3)中国的更相减损术

  1. //更相减损术
  2.     public int findDivisor(int a, int b) {
  3.         if (a == b) {
  4.             return a;
  5.         }
  6.         int big = a > b ? a : b;
  7.         int small = a < b ? a : b;
  8.         if ((a & 1) == 0 && (b &1) == 0) {
  9.             return findDivisor(a >> 1, b >> 1) << 1;
  10.         } else if ((a & 1) == 0 && (b &1) != 0) {
  11.             return findDivisor(a >> 1, b);
  12.         } else if ((a & 1) != 0 && (b &1) == 0) {
  13.             return findDivisor(a, b >> 1);
  14.         } else {
  15.             return findDivisor(big - small, small);
  16.         }
  17.     }