任意输入两个数字求最大公约数（Java)

83 阅读 0 评论 55 点赞

我是靠谱客的博主平淡小笼包，最近开发中收集的这篇文章主要介绍任意输入两个数字求最大公约数（Java)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

更相减损法

public class Demo5 {
    public static void main(String[] args) {
        // 使用更相减损法求 m n 的最大公因数
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入数字m：");
        int m = sc.nextInt();
        System.out.println("请输入数字n：");
        int n = sc.nextInt();
        // 写一个方法
        int GCM = fun(m,n);
        System.out.println("最大公因数为：" + GCM);
    }
    public static int fun (int m, int n) {
        // 先获得绝对值，保证负数也可以求
        m = Math.abs(m);
        n = Math.abs(n);
        // 区分数值大小，为后面终止条件做准备，定义出最大值和最小值
        int min = m > n ? n : m;
        int max = m > n ? m : n;

        // 第一步：如果两个数是偶数，则先用2进行约分，并存储约去的2的乘积
        int GCM = 1;
        while (min % 2 == 0 && max % 2 == 0) {
            min /= 2;
            max /= 2;
            GCM *= 2;
        }

        // 第二步：用较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数
        // 继续这个操作，直到所得的减数和差相等为止。（或者多循环一次，判断相减差为 0）
        while (max - min > 0) {
            int deference = max - min; // 获得差数
            // 更相减损，将差数和较小数比较；大的重新赋给 max，小的赋给min，注意顺序
            max = min > deference ? min : deference;
            min = min < deference ? min : deference;
        }
        return GCM * min;
    }
}