黑马程序员技术交流社区

标题: 最大公约数算法 [打印本页]

作者: 宫曼曼    时间: 2019-6-26 23:23
标题: 最大公约数算法
public class GCD {
   
    /**
     * 求最大公约数 辗转相除法(欧几里德算法) 例如,求(319,377): ∵ 319÷377=0(余319)
     * ∴(319,377)=(377,319); ∵ 377÷319=1(余58) ∴(377,319)=(319,58); ∵
     * 319÷58=5(余29) ∴ (319,58)=(58,29); ∵ 58÷29=2(余0) ∴ (58,29)= 29; ∴
     * (319,377)=29。 可以写成右边的格式。
     * 用辗转相除法求几个数的最大公约数,可以先求出其中任意两个数的最大公约数,再求这个最大公约数与第三个数的最大公约数,依次求下去,直到最后一个数为止。
     * 最后所得的那个最大公约数,就是所有这些数的最大公约数。
     *
     * @param m
     * @param n
     * @return
     */
    public static int GCD(int m, int n) {
        int result = 0;
        while (n != 0) {
            result = m % n;
            m = n;
            n = result;
        }
        return m;


    }


    /**
     * 质因数分解法:把每个数分别分解质因数,再把各数中的全部公有质因数提取出来连乘,所得的积就是这几个数的最大公约数。 (小学学的方法)
     *
     * @param m
     * @param n
     * @return
     */
    public static int PrimeGCD(int m, int n) {
        int result = 1;
        Set<Integer> set1 = getFactor(m);
        Set<Integer> set2 = getFactor(n);
        // 取交集
        set1.retainAll(set2);
        // 取最大
        result = Collections.max(set1);
        return result;
    }
    /**
     * 更相减损术”,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。”
     * @param m
     * @param n
     * @return
     */
    public static int equalGCD(int m, int n) {
        while (m != n) {
            if (m > n)
                m -= n;
            else
                n -= m;
        }
        return m;


    }


    /**
     * 获取某一数值的所有因数
     *
     * @param m
     * @return
     */
    private static Set<Integer> getFactor(int m) {
        Set<Integer> set = new HashSet<Integer>();
        for (int i = 2; i <= m; i++) {
            if (m % i == 0) {
                set.add(i);
            }
        }
        return set;
    }
    public static void main(String[] args) {
//      int result = GCD(32, 48);
//      int result = PrimeGCD(32, 48);
      int result = equalGCD(32, 48);
      System.out.println(result);
    }
}





欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2