求最大公约数(公因子)多种java实现方法

2024-03-04数据结构与算法1 分钟218 次阅读
AI 摘要salmon-ai

本文详细解析了最大公约数(公因子)的概念及四种 Java 求法,包括辗转相除法、

前言

在做算法题的时候,经常会遇到需要求公因数,而其中最大的数就叫最大公因数,也称最大公约数、最大公因子。
公约数:几个整数,公有的约数,叫做这几个数的公约数;其中最大的一个,叫做这几个数的最大公约数。例如:12、16的公约数有1、2、4,其中最大的一个是4,4是12与16的最大公约数。

方法一:辗转相除法

如求(9, 15)的 最大公因子
9 / 15 = 0….9
15 / 9 = 1….6
9 / 6 = 1……3
6 / 3 = 2……0
像这样辗转相除, 直到出现余数为零停止, 那么最后的除数就是最大公因子, 即最大公因子等于 3

java 复制代码
    public static int gcd1(int a, int b) {
        return a % b == 0 ? b : gcd1(b, a % b);
    }

方法二:更相减损法

如求(9, 15)的 最大公因子
15 - 9 = 6
9 - 6 = 3
6 - 3 = 3
像这样一直用最大的数减去最小的数,直到被减数和差相等,那么减数就是最大公因子, 即最大公因子等于 3

java 复制代码
    public static int gcd2(int a, int b) {
        int minVal = Math.min(a, b); //找出a与b中最小数
        int maxVal = Math.max(a, b); //找出a与b中最大数
        return minVal == maxVal - minVal ? minVal : gcd2(minVal, maxVal - minVal);
    }

方法三:短除法

短除法求最大公约数,先用这几个数的公约数连续去除,一直除到所有的商互质为止,然后把所有的除数连乘起来,所得的积就是这几个数的最大公约数。
如求(12, 24)的最大公因子
12 24 | 2
6 12 | 2
3 6 | 3
1 2
最后 1 和 2 都是质数, 最大公因子就等于 223 = 12

java 复制代码
    static int max = 1;

    public static int gcd3(int a, int b) {
        int minVal = Math.min(a, b);
        for (int i = 2; i <= minVal; i++) {
            // 找出最小的公因子
            if (a % i == 0 && b % i == 0) {
                max *= i;
                gcd3(a / i, b / i);
                return max;
            }
        }
        // 走到这,说明上边已经没有2以上的公因数了
        return max;
    }

方法四:普通方法

从(a, b)中的最小值 (假设 这里为a) 开始从后往前依次遍历, 查找都能被b和a都整除的数,这个数就是 最大公因子.
如(9, 15)的最大公因子
9 , 8 , 7, 6, 5, 4, 3当循环到3的时候发现 9%3 等于零, 15%3等于零,那么 3 就是最大公因子

java 复制代码
    public static int gcd4(int a, int b) {
        int minVal = Math.min(a, b);
        for (int i = minVal; i >= 2; i--) {
            if (a % i == 0 && b % i == 0) {
                return i;
            }
        }
        return 1;
    }
觉得有用就点个赞,不用登录也能读

评论

0 条
登录 之后才能评论
—
还没有评论,来说第一句