m和n的最大公约数就是能够同时整除他它们的最大正整数。
第一种：欧几里得算法求最大公约数：
/* 欧几里得算法： * 两个不全为0的非负整数m,n的最大公约数记为 gcd(m,m),代表能够整除m和 * n的最大正整数。 * gcd(m,n) = gcd(n, m mod n) (mod 是取余，或取模%) * 重复循环上面的等式，直到 m mod n 等于0。最后的m值就是gcd. * 为什么？gcd(m, 0) = m. m 最后的取值是 m, n的初值的最大公约数。 * gcd(m, 0) 意味着 （前者m % 后者n） == 0，即能整除了。此时的m * 就是最大公约数。 * 举个栗子：gcd(10,6) = gcd(6,4) = gcd(4,2) = gcd(2,0) = 2; * gcd(60,24) = gcd(24,12) = gcd(12,0) = 12; * * 换个算法文字描述如下： * 需求：用欧几里得算法求最大公约数,gcd(m,n); * 第一步：对于给定的m,n，不全为0;m>n;如果n = 0,则返回m值作为结果， * 同时计算过程结束。否则，进入下一步。 * 第二步：将m除以n,取余数赋值给r; * 第三步：将n的值赋值给m,将余数r赋值给n;返回第一步。 * */ /* pseudocode: * gcdByEuclid(m,n) * //使用欧几里得算法计算gcd(m,n) * //输入：两个不全为0的非负整数 * //输出：m, n的最大公约数 * while n ≠ 0 do * r = m mod n * m = n * n = r * return m * / //Java代码实现 // function to get gcd public static int gcdByEuclid(int m, int n) { int r; while (n != 0) { r = m % n; m = n; n = r; } return m; }第二种：连续整数检测法 求最大公约数：
/* 根据定义,m 和n 的最大公约数是能够同时整除它们的最大正整数。其中，这个最大公约数不大于m和n的较小者。 令temp = min{m,n}; 检查下t是否能够整除m和n;如果能，t就是最大公约数； 如果不能，将t 减去1，再作判断，继续尝试直到出现一个值能同时整除m 和 n; 而且，t>=1(当t = 1时，判断肯定成立，因为1能整除任何正整数。） */ /* 连续整数法求最大公约数算法 文字描述： 第一步：将min{m, n} 赋值给temp; 第二步：m 除以 t, 取余数。如果余数为0，进入第三步。否则，进入第四步。 第三步：m 除以t,取余数，如果余数为0，返回temp作为结果; 否则，进入第四步。 第四步：把 temp 值减1，返回第二步。 */ pseudocode： gcdByContinuouslyDivison(m, n) //使用连续整除的方法计算gcd(m,n) //输入两个正整数m,n //输出m, n 的最大公约数 int temp = min{m, n} while(m mod temp ≠ 0 or n mod temp ≠ 0) do temp-- return temp //Java代码实现 // function to get gcd public static int gcdByContinuousDivision(int m, int n) { // 第一步：将min{m, n} 赋值给temp; int temp = m; if (m > n) { temp = n; } // 判断m%temp, n%temp， while (m % temp != 0 || n % temp != 0) { //第四步：把 temp 值减1 temp--; } return temp; }