最大公约数和最小公倍数

题目

输入两个正整数 m 和 n，求其最大公约数和最小公倍数

运行示例

请输入第一个正整数：48
请输入第二个正整数：18
最大公约数：6
最小公倍数：144

请输入第一个正整数：13
请输入第二个正整数：7
最大公约数：1
最小公倍数：91

👈点击左箭头查看答案（一定要在自己思考并实现后再看参考答案哦！）

import java.util.Scanner;

public class Demo06 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        System.out.print("请输入第一个正整数：");
        int a = in.nextInt();
        System.out.print("请输入第二个正整数：");
        int b = in.nextInt();

        // 输入校验（题目要求正整数）
        if (a <= 0 || b <= 0) {
            System.out.println("错误：请输入两个正整数！");
            return;
        }

        int gcd = gcd(a, b);
        long lcm = (long) a * b / gcd; // 防止 a*b 溢出（用 long）

        System.out.println("最大公约数：" + gcd);
        System.out.println("最小公倍数：" + lcm);
    }

    /**
     * 使用欧几里得算法计算最大公约数（GCD）
     */
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
}

算法说明

欧几里得算法（辗转相除法）

原理：

gcd(a, b) = gcd(b, a mod b)，直到 b = 0，此时 a 即为 GCD。

示例：gcd(48, 18)

48 % 18 = 12 → gcd(18, 12)
18 % 12 = 6  → gcd(12, 6)
12 % 6 = 0   → gcd(6, 0) → 返回 6

源本科技 | 码上会

题目

运行示例

算法说明