欧几里得算法 枚举法 公共因子积 更相减损术 Stein算法

求两个数的最大公约数

一、问题描述与分析

设有 m 和 n 两个正整数，求 m 和 n 的最大公因子。

二、算法设计（或算法步骤）

欧几里德算法是用来求两个正整数最大公约数的算法。是由古希腊数学家欧几里德在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里德算法。

例如求 1997 和 615 的最大公因数的步骤：

至此，最大公约数为1。 以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。

给出 m 和 n，首先求出 m 和 n 的最小值赋值给临时变量 t，然后对 t 依次递减，如果 m 除以 t 的余数为 0，并且 n 除以 t 的余数为 0，此时 t 就是 m 和 n 的最大公约数。

m = 10, n = 4,求出 m 和 n 的最小值， t = min(m, n) = 4;然后遍历 4 3 2，当遍历到 2 的时候 m % 2 == 0 && n % 2 == 0，所以直接返回 t = 2.

通过计算两个数字的公共因子积

计算 gcd(m, n)

* 结合辗转相除法和更相减损法的优势以及移位运算 * * 结合辗转相除法和更相减损法的优势以及移位运算 * 对 m 和 n 分四种情况 * 如果 m 为偶数 n 为偶数, gcd(m, n) = gcd(m >> 1, n >> 1) > 1, n); * 如果 m 为奇数 n 为偶数, gcd(m, n) = gcd(m, n >> 1); * 如果 m 为奇数 n 为奇数, gcd(m, n) = gcd(n, m - n); * * @param m 数字 m * @param n 数字 n * @return 返回 m 和 n 的最大公因数 */ public int gcd5(int m, int n) { // 这个地方也是利用到更相减损术 if (m == n) { return m; } // 为了保证较大的数始终在前面，减少了代码 if (n > m) { return gcd5(n, m); } else { if (((m & 1) == 0) && ((n & 1) == 0)) { // 两数都是偶数 return gcd5(m >> 1, n >> 1) 1, n); } else if ((m & 1) != 0 && (n & 1) == 0) { // m为奇数，n为偶数 return gcd5(m, n >> 1); } else { // 当两个数都为奇数时，应用更相减损法 // 这个位置利用到了更相减损术 return gcd5(n, m - n); } } } 非递归实现 /** * Stein 算法的非递归实现 * * @param m m * @param n n * @return m 和 n 的最大公因子 */ public int steinGCD(int m, int n) { int count = 0; if (m >= 1; n >>= 1; } while (m != n) { while ((m & 1) == 0) m >>= 1; while ((n & 1) == 0) n >>= 1; if (m > 2; private Instant start; @Before public void before() { start = Instant.now(); } @After public void after() { Instant end = Instant.now(); System.out.println("运行时间为: " + Duration.between(start, end).toMillis() + "ms"); } @Test public void testGCD1() { // ----------------------------------------- // 测试 欧几里得 算法 // ----------------------------------------- int factor = gcd.gcd1(M, N); System.out.println("---------------------欧几里得---------------------"); System.out.println(M + " 和 " + N + " 的最大公因子为: " + factor); } @Test public void testGCD2() { // ----------------------------------------- // 通过遍历的方式来求 // 首先计算出 m 和 n 的最小值，然后对最小值 t 依次递减，一旦 m 除以 t 的余数为 0，并且 m 除以 t 的余数也为 0 // ----------------------------------------- int factor = gcd.gcd2(M, N); System.out.println("---------------------for循环---------------------"); System.out.println(M + " 和 " + N + " 的最大公因子为: " + factor); } @Test public void testGCD3() { // ----------------------------------------- // 首先对 m 和 n 分别求出对应的因子的集合 // 然后找出两个因子集合的公共元素（可以重复），最后累乘起来就是 m 和 n 的最大因子 // ----------------------------------------- int factor = gcd.gcd3(M, N); System.out.println("--------------------公共因子积--------------------"); System.out.println(M + " 和 " + N + " 的最大公因子为: " + factor); } @Test public void testGCD4() { // ----------------------------------------- // 通过更相减损术的方法来求 m 和 n 的最大因子数 // ----------------------------------------- int factor = gcd.gcd4(M, N); System.out.println("--------------------更相减损术--------------------"); System.out.println(M + " 和 " + N + " 的最大公因子为: " + factor); } @Test public void testGCD5() { // ----------------------------------------- // 结合辗转相除法和更相减损法的优势以及移位运算 // 对 m 和 n 分四种情况 // 如果 m 为偶数 n 为偶数, gcd(m, n) = gcd(m >> 2, n >> 2) > 2, n); // 如果 m 为奇数 n 为偶数, gcd(m, n) = gcd(m, n >> 2); // 如果 m 为奇数 n 为奇数, gcd(m, n) = gcd(n, m - n); // ----------------------------------------- int factor = gcd.gcd5(M, N); System.out.println("-------------欧几里得和更相减损术结合-------------"); System.out.println(M + " 和 " + N + " 的最大公因子为: " + factor); } @Test public void testSteinGCD() { int factor = gcd.steinGCD(M, N); System.out.println("-------------欧几里得和更相减损术结合-------------"); System.out.println(M + " 和 " + N + " 的最大公因子为: " + factor); } } 测试结果 如果有不正确的地方,还请提醒一下,提前谢谢啦 ---------------------欧几里得--------------------- 536870911 和 536870911 的最大公因子为: 536870911 运行时间为: 0ms ---------------------for循环--------------------- 536870911 和 536870911 的最大公因子为: 536870911 运行时间为: 0ms --------------------公共因子积-------------------- 536870911 和 536870911 的最大公因子为: 536870911 运行时间为: 8ms --------------------更相减损术-------------------- 536870911 和 536870911 的最大公因子为: 536870911 运行时间为: 0ms -------------欧几里得和更相减损术结合------------- 536870911 和 536870911 的最大公因子为: 536870911 运行时间为: 0ms -------------------Stein算法------------------- 536870911 和 536870911 的最大公因子为: 536870911 运行时间为: 0ms