求两个数的最大公约数

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

求两个数的最大公约数

一、问题描述与分析

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

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

欧几里得算法

算法简介

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

算法过程描述

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

1997 / 615 = 3 (余 152)
615 / 152 = 4 (余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)

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

算法实现

/** * 利用 欧几里得算法 求 m 和 n 的最大公约数,并且 m >= n * * @param m m * @param n n * @return m 和 n 的最大公约数 */
public int gcd(int m, int n) { 
    while (n != 0) { 
        int temp = m % n;
        m = n;
        n = temp;
    }
    return m;
}

枚举法

算法简介

给出 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.

算法实现

/** * 通过遍历的方式来求 m 和 n 的最大公约数 * * @param m m * @param n n * @return m 和 n 的最大公约数 */
public int gcd2(int m, int n) { 
    // 第一步:将 min{m, n}的值赋值给 t
    int t = Math.min(m, n);
    for (; t >= 2; t--) { 
        // 第二步和第三步,如果 m 除以 t 余数为 0 并且 n 除以 t 余数为 0,直接返回 t
        if (m % t == 0 && n % t == 0) { 
            return t;
        }
        // 否则 t--,返回第二步和第三步
    }
    return 1;
}

公共因子积

算法简介

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

算法描述

计算 gcd(m, n)

• 第一步:找出 m 的全部质因数
• 第二步:找出 n 的全部质因数
• 第三步:从第一步和第二步求得的质因数分解式中找出所有的公因数(如果p是一个公因数,而且在m和n的质因数分解式分别出现过pm和pn 次,那么应该将p重复min{pm, pn}次).
• 第四步:将第三步中找到的质因数相乘,其结果作为给定数字的最大公约数.

算法实现

    public int gcd3(int m, int n) { 
        Instant start = Instant.now();
        int[] marr = factorArr(m);
        int[] narr = factorArr(n);

        // ---------------------------------------------------------------------
        // 处理两个数组的公共元素
        // ---------------------------------------------------------------------
        // 求出 marr 和 narr 的最大值

        Map<Integer, Integer> mMap = new HashMap<>(marr.length);
        Map<Integer, Integer> nMap = new HashMap<>(narr.length);

        // 处理 marr
        for (int i = 0; i < marr.length; ) { 
            int index = i;
            int count = 0;
            while (index < marr.length && marr[index] == marr[i]) { 
                count++;
                index++;
            }
            mMap.put(marr[i], count);
            i = index;
        }

        // 处理 narr
        for (int i = 0; i < narr.length; ) { 
            int index = i;
            int count = 0;
            while (index < narr.length && narr[index] == narr[i]) { 
                count++;
                index++;
            }
            nMap.put(narr[i], count);
            i = index;
        }

        int sum = 1;

        // 可以遍历任意一个 map ，来找出公共元素的个数
        for (Map.Entry<Integer, Integer> entry : mMap.entrySet()) { 
            // 取出 value
            int value = entry.getKey();
            // 取出个数
            int count = entry.getValue();
            // 取出另外一个集合中对应 value 值出现的次数
            int anotherCount = nMap.get(value) == null ? 0 : nMap.get(value);
            // 两个因子数组相同因子出现次数的较小值
            int minCount = Math.min(count, anotherCount);

            sum *= minCount * value == 0 ? 1 : Math.pow(value, minCount);
        }

        return sum;
    }

    /** * 返回 value 的全部因子,以数组的形式返回 * * @param value value 值 * @return value 的全部因子,以数组的形式返回 */
    private int[] factorArr(int value) { 
        List<Integer> list = new ArrayList<>();
        for (int i = 2; i <= Math.sqrt(value); i++) { 
            if (value % i == 0) { 
                list.add(i);
                value /= i;
                i--;
            }
        }
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }

更相减损术

算法简介

算法描述

• 第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
• 第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
• 则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。

算法实现

/** * 使用更相减损法求 m 和 n 的最大公约数 * * @param m 数字 m * @param n 数字 n * @return m 和 n 的最大公约数 */
public int gcd4(int m, int n) { 
    // 两个数字不相等时，继续进行运算，
    while (m != n) { 
        if (m > n) m -= n;
        else n -= m;
    }
    return m;
}

Stein算法

算法简介

欧几里德算法是计算两个数最大公约数的传统算法，无论从理论还是从实际效率上都是很好的。但是却有一个致命的缺陷，这个缺陷在素数比较小的时候一般是感觉不到的，只有在大素数时才会显现出来：一般实际应用中的整数很少会超过64位（当然现在已经允许128位了），对于这样的整数，计算两个数之间的模是很简单的。对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，而计算64位以下的整数模，也不过几个周期而已。但是对于更大的素数，这样的计算过程就不得不由用户来设计，为了计算两个超过64位的整数的模，用户也许不得不采用类似于多位数除法手算过程中的试商法，这个过程不但复杂，而且消耗了很多CPU时间。对于现代密码算法，要求计算128位以上的素数的情况比比皆是，比如说RSA加密算法至少要求500bit密钥长度，设计这样的程序迫切希望能够抛弃除法和取模。
————————————————
版权声明：本文为CSDN博主「Holmofy」的原创文章，遵循 CC 4.0 BY-SA 版权协 议，转载请附上原文出处链接及本声明。
原文链接:
Stein算法很好的解决了欧几里德算法中的这个缺陷，Stein算法只有整数的移位和加减法。

算法描述

如果 m 为偶数 n 为偶数, gcd(m, n) = gcd(m >> 1, n >> 1) << 1;
如果 m 为偶数 n 为奇数, gcd(m, n) = gcd(m >> 1, n);
如果 m 为奇数 n 为偶数, gcd(m, n) = gcd(m, n >> 1);
如果 m 为奇数 n 为奇数, gcd(m, n) = gcd(n, m - n);

算法实现

/** * 求两个正整数的最大公因数 * <p> * 结合辗转相除法和更相减损法的优势以及移位运算 * * 结合辗转相除法和更相减损法的优势以及移位运算 * 对 m 和 n 分四种情况 * 如果 m 为偶数 n 为偶数, gcd(m, n) = gcd(m >> 1, n >> 1) << 1; * 如果 m 为偶数 n 为奇数, gcd(m, n) = gcd(m >> 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;
        } else if ((m & 1) == 0 && (n & 1) != 0) { 
            // m为偶数，n为奇数
            return gcd5(m >> 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 < n) return steinGCD(n , m);
    while ((m & 1) == 0 && (n & 1) == 0) { 
        count++;
        m >>= 1;
        n >>= 1;
    }
    while (m != n) { 
        while ((m & 1) == 0) m >>= 1;
        while ((n & 1) == 0) n >>= 1;
        if (m < n) { 
            m ^= n;
            n ^= m;
            m ^= n;
        }
        // 进行一次更相减损术
        int temp = m - n;
        m = n;
        n = temp;
    }
    return m << count;
}

测试代码

package xyz.snowflake.chapter01.example.gcd;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;

import java.time.Duration;
import java.time.Instant;

/** * @author snowflake * @email 278121951@qq.com * @create-date 2019-09-02 16:39 */
public class GCDTest { 

    private GCD gcd = new GCD();

    private final int M = Integer.MAX_VALUE >> 2;
    private final int N = Integer.MAX_VALUE - 2 >> 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;
        // 如果 m 为偶数 n 为奇数, gcd(m, n) = gcd(m >> 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