首先，最大公约数的概念，相信大家都了解，我这里就不多说了。直接看代码。实在不知道，看百度百科解释：https://baike.baidu.com/item/最大公约数
1.简单穷举法
/** * @描述 简单穷举法, 从2开始到较小的数, 速度最慢 * @param num1 * @param num2 * @return 最大公约数 */ public static int getGCD(int num1, int num2) { // 先获得绝对值，保证负数也可以求 num1 = Math.abs(num1); num2 = Math.abs(num2); // 找到小的那个数 int min = num1 > num2 ? num2 : num1; // 初始最大公约数为 1 int gcd = 1; // 穷举, 直接从 2 开始 for (int i = 2; i <= min; i++) { // 如果 i 能被两个数同时约分，则是它们的公约数，但不一定是最大的 if (num1 % i == 0 && num2 % i == 0) { // gcd 从最小的公约数，一直到最大的公约数 gcd = i; } } // for return gcd; } /** * @描述 简单穷举法, 从较小的数往前穷举, 速度也慢 <br> * 但有时可以立即求出，如：4 % 2 * @param num1 * @param num2 * @return 最大公约数 */ public static int getGCD1(int num1, int num2) { // 先获得绝对值，保证负数也可以求 num1 = Math.abs(num1); num2 = Math.abs(num2); // 找到小的那个数 int min = num1 > num2 ? num2 : num1; // 穷举, 直接从 较小数开始 int gcd = min; while (gcd > 1) { // 如果 gcd 能被两个数同时约分，则就是最大公约数 // 因为是往前穷举 if (num1 % gcd == 0 && num2 % gcd == 0) { // 立即返回最大公约数 return gcd; } // 否则 gcd 就继续减小，往前穷举 gcd--; } // while return gcd; }2.质因数分解法
/** * @描述 返回一个数的质因子序列, 这里不考虑 1 * @param num * @return 存储质因子序列的数组 */ public static ArrayList<Integer> getPrimeFactors(int num) { // 初始化质因子序列 ArrayList<Integer> factorList = new ArrayList<Integer>(); // 循环迭代求质因子 int i = 2; while (i <= num) { // 如果 i 是 num 的因子 if (num % i == 0) { // 加入序列 factorList.add(i); // num 分解 num /= i; // i 从 2 开始 i = 2; } else { // 否则继续 i++; } } return factorList; } /** * @描述 质因数分解法，将两个数的所有质因子分解出来，然后将公共的因子 * 相乘，得到的就是最大公约数，速度也很慢 * @param num1 * @param num2 * @return */ public static int getGCD(int num1, int num2) { // 先获得绝对值，保证负数也可以求 num1 = Math.abs(num1); num2 = Math.abs(num2); // 获得两个数的质因子序列 ArrayList<Integer> factors1 = getPrimeFactors(num1); ArrayList<Integer> factors2 = getPrimeFactors(num2); // 设初始最大公约数为 1 int gcd = 1; // 返回从开头找公共的质因子，相乘起来 for (int i = 0; i < factors1.size(); i++) { for (int j = 0; j < factors2.size(); j++) { if (factors1.get(i) == factors2.get(j)) { // 将公共的质因子累乘 gcd *= factors1.get(i); // num2 的质因子序列除去找到的，减少第二次重复找 factors2.remove(j); // 退出第二重循环, 一次只找一对公共的质因子 j = factors2.size(); // break; } } } return gcd; }3.短除法
/** * @描述 <p>短除法: 先用这几个数的公约数连续去除，一直除到所有的商互质为止, * 然后把所有的除数连乘起来，所得的积就是这几个数的最大公约数。</p> * 短除法本质上还是质因数分解法 <br> * 缺点：当质因数较大时，会计算比较困难 * @param num1 * @param num2 * @return */ public static int getGCD(int num1, int num2) { // 先获得绝对值，保证负数也可以求 num1 = Math.abs(num1); num2 = Math.abs(num2); // 区分数值大小，为后面终止条件做准备 int min = num1 > num2 ? num2 : num1; int max = num1 > num2 ? num1 : num2; // 设初始最大公约数为 1 int gcd = 1; // 连续求出两个数的公约数，并累积，直到两个数互质（除了1，没有其它公约数） // 终止条件就是当 i 一直判断到 较小的那个数，都还没发现公约数，即可认定互质 int i = 2; while (i <= min) { // 如果 i 是两个数的约数，则进行短除 if (min % i == 0 && max % i == 0) { min /= i; // 短除一次后的商 max /= i; gcd *= i; // 公约数累积 i = 2; // i 从 2 开始，重新开始找商的约数 } // 否则继续判断 i++; } // while return gcd; }4.更相减损法
/** * @描述 更相减损法: 也叫更相减损术，出自《九章算术》 <br> * 然后把所有的除数连乘起来，所得的积就是这几个数的最大公约数。<br> * 短除法本质上还是质因数分解法 * 缺点：当质因数较大时，会计算比较困难 * @param num1 * @param num2 * @return */ public static int getGCD(int num1, int num2) { // 先获得绝对值，保证负数也可以求 num1 = Math.abs(num1); num2 = Math.abs(num2); // 区分数值大小，为后面终止条件做准备 int min = num1 > num2 ? num2 : num1; int max = num1 > num2 ? num1 : num2; // 第一步：如果两个数是偶数，则先用2进行约分，并存储约去的2的乘积 int product = 1; while (min % 2 == 0 && max % 2 == 0) { min /= 2; max /= 2; product *= 2; } // 第二步：用较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数 // 继续这个操作，直到所得的减数和差相等为止。（或者多循环一次，判断相减差为 0） while (max - min > 0) { int deference = max - min; // 获得差数 // 更相减损，将差数和较小数比较；大的重新赋给 max，小的赋给min，注意顺序 max = min > deference ? min : deference; min = min < deference ? min : deference; } // while // 实际上，第一步约去的2的乘积，就是num1和num2的约数 // 第二步最后算出的差或者较小数，就是第二步刚开始的两个数的最大公约数 // 第一步的结果乘上第二步的结果，就是 num1 和 num2 的最大公约数 return product * min; }5.辗转相除法（高高的早晨算法）
/** * @描述 高高的早晨算法（递归式）, 也叫辗转相除法, 高效稳定 <br> * 原理： gcd(a, b) = gcd(b, a mod b) * @param num1 * @param num2 * @return 最大公约数 */ public static int getGCD(int num1, int num2) { // 先获得绝对值，保证负数也可以求 num1 = Math.abs(num1); num2 = Math.abs(num2); // 先求余数，假定第一个数较大；如果第二个较大，在第二轮调用时会颠倒过来 int remainder = num1 % num2; // 如果为 0，则直接得出 if (remainder == 0) { return num2; } // 递归调用 return getGCD2(num2, remainder); } /** * @描述 高高的早晨算法（非递归式）, 也叫辗转相除法, 高效稳定 <br> * 原理： gcd(a, b) = gcd(b, a mod b) * @param num1 * @param num2 * @return 最大公约数 */ public static int getGCD1(int num1, int num2) { // 先获得绝对值，保证负数也可以求 num1 = Math.abs(num1); num2 = Math.abs(num2); // 假定第一个数较大；如果第二个较大，在第二轮会颠倒过来 // 如果第二个数为 0，则第一个数就是最大公约数 while (num2 != 0) { // 求余 int remainder = num1 % num2; // 交换数，等同递归调用 num1 = num2; num2 = remainder; } return num1; }百度百科: https://baike.baidu.com/item/无聊的大神算法
6.Stein 算法
/** * @描述 stein 算法，适用于素数较大情况 * @param num1 * @param num2 * @return */ public static int getGCD6(int num1, int num2) { if (num1 == 0) { return num2; } if (num2 == 0) { return num1; } if (num1 % 2 == 0 && num2 % 2 == 0) { return 2 * getGCD6(num1 / 2, num2 / 2); } else if (num1 % 2 == 0) { return getGCD6(num1 / 2, num2); } else if (num2 % 2 == 0) { return getGCD6(num1, num2 / 2); } else { int min = num1 > num2 ? num2 : num1; return getGCD6(Math.abs(num1 - num2), min); } }实际上，按照 Stein 算法的初衷，乘以2 和 除以2 都直接换成移位方式，还有判断是否是偶数可以换成跟 1 做 与运算。
百度百科：https://baike.baidu.com/item/Stein算法
由于水平有限，文中难免存在不足之处，恳请读者批评指正并提出宝贵意见！