java 最大公约数和最小公倍数-杰瑞科技汇

Java 最大公约数和最小公倍数实现

在Java中，计算两个数的最大公约数(GCD)和最小公倍数(LCM)有几种常见的方法,下面我将介绍几种实现方式。

（图片来源网络，侵删）

使用欧几里得算法求最大公约数

欧几里得算法是最常用的求GCD的方法：

public class GCDAndLCM {
    // 使用欧几里得算法求GCD
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    // 递归实现欧几里得算法
    public static int gcdRecursive(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcdRecursive(b, a % b);
    }
}

计算最小公倍数

最小公倍数可以通过最大公约数来计算：

public class GCDAndLCM {
    // ... 之前的gcd方法 ...
    // 计算最小公倍数
    public static int lcm(int a, int b) {
        if (a == 0 || b == 0) {
            return 0; // 0和任何数的LCM是0
        }
        return Math.abs(a * b) / gcd(a, b);
    }
}

完整示例

下面是一个完整的示例,包含测试代码：

public class GCDAndLCM {
    public static void main(String[] args) {
        int num1 = 12;
        int num2 = 18;
        System.out.println("使用迭代方法:");
        System.out.println("GCD of " + num1 + " and " + num2 + " is: " + gcd(num1, num2));
        System.out.println("LCM of " + num1 + " and " + num2 + " is: " + lcm(num1, num2));
        System.out.println("\n使用递归方法:");
        System.out.println("GCD of " + num1 + " and " + num2 + " is: " + gcdRecursive(num1, num2));
        // 测试负数
        num1 = -12;
        num2 = 18;
        System.out.println("\n测试负数:");
        System.out.println("GCD of " + num1 + " and " + num2 + " is: " + gcd(num1, num2));
        System.out.println("LCM of " + num1 + " and " + num2 + " is: " + lcm(num1, num2));
    }
    // 使用欧几里得算法求GCD
    public static int gcd(int a, int b) {
        a = Math.abs(a); // 处理负数
        b = Math.abs(b); // 处理负数
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    // 递归实现欧几里得算法
    public static int gcdRecursive(int a, int b) {
        a = Math.abs(a); // 处理负数
        b = Math.abs(b); // 处理负数
        if (b == 0) {
            return a;
        }
        return gcdRecursive(b, a % b);
    }
    // 计算最小公倍数
    public static int lcm(int a, int b) {
        if (a == 0 || b == 0) {
            return 0; // 0和任何数的LCM是0
        }
        return Math.abs(a * b) / gcd(a, b);
    }
}

使用Java 8的BigInteger处理大数

如果需要处理非常大的整数，可以使用BigInteger类：

（图片来源网络，侵删）

import java.math.BigInteger;
public class BigGCDAndLCM {
    public static void main(String[] args) {
        BigInteger num1 = new BigInteger("12345678901234567890");
        BigInteger num2 = new BigInteger("98765432109876543210");
        BigInteger gcd = num1.gcd(num2);
        BigInteger lcm = num1.multiply(num2).divide(gcd);
        System.out.println("GCD: " + gcd);
        System.out.println("LCM: " + lcm);
    }
}

扩展到多个数的GCD和LCM

要计算多个数的GCD和LCM,可以依次计算：

public class MultipleNumbersGCDLCM {
    public static void main(String[] args) {
        int[] numbers = {12, 18, 24, 36};
        int resultGCD = numbers[0];
        int resultLCM = numbers[0];
        for (int i = 1; i < numbers.length; i++) {
            resultGCD = gcd(resultGCD, numbers[i]);
            resultLCM = lcm(resultLCM, numbers[i]);
        }
        System.out.println("GCD of all numbers: " + resultGCD);
        System.out.println("LCM of all numbers: " + resultLCM);
    }
    // ... 前面的gcd和lcm方法 ...
}

方法涵盖了Java中计算最大公约数和最小公倍数的各种实现方式，包括迭代、递归、处理大数以及多个数的计算。