求两个数的最大公约数GCD与最小公倍数LCM

Love The Way You Lie 2022-02-19 08:36 228阅读 0赞

## code ##

import java.util.Scanner;
    import java.util.List;
    import java.util.LinkedList;
    
    /**
     * 编写图形界面下的JavaApplication程序，计算M和N的最大公约数。
     */
    public class Test {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            System.out.println("请输入两个整数，用空格或换行隔开：");
            int a = sc.nextInt();
            int b = sc.nextInt();
            int[] arr = getGcdAndLcM(a, b);
            System.out.printf("%s 和 %s 的最大公约数(GCD)为：%s\n", a, b, arr[0]);
            System.out.printf("%s 和 %s 的最小公倍数(LCM)为：%s\n", a, b, arr[1]);
            sc.close();
        }
    
        /**
         * 获取数值a和b的最大公约数和最小公倍数。
         * @return: arr，长度为2的数组
         *   arr[0]: GCD(Greatest Common Divisor)，最大公约数。
         *   arr[1]: LCM(Lowest Common Multiple)，最小公倍数。
         */
        static int[] getGcdAndLcM(int a, int b) {
            // 过滤客户端参数，保证：a > b
            if (a < b) {
                int tmp = a;
                a = b;
                b = tmp;
            }
            List<Integer> list = decompositionDivisor(a, b);
            int gcd =  1;
            int stopPos = list.size() - 2;
            for (int i = 0; i < stopPos; i++) {            
                gcd *= list.get(i);
            }
            int lcm = gcd * list.get(stopPos) * list.get(stopPos + 1);
            return new int[] {gcd, lcm};
        }
        
        /**
         * 分解质因数
         * @param big 较大的数
         * @param small 较小的数
         * @return 分解结果。其中：
         *       arr[0] ~ arr[length-3] 存储big和small的公因数。
         *       arr[length-2]和arr[length-1]存储big和small分解之后的结果。
         *       位置可自定，由函数内部的实现而定。
         */
        static List<Integer> decompositionDivisor(int big, int small) {
            List<Integer> list = new LinkedList<>();
    
            // big可以直接被small整除
            if (canExactDivision(big, small)) {
                list.add(small);
                list.add(1);
                list.add((int) (big / small));
                return list;
            }
    
            // big 不能被small整除。
            int divisor = 2;
            while (divisor < small) {
                if (canExactDivision(big, divisor) && canExactDivision(small, divisor)) {
                    // System.out.printf("%s %s 可以被 %s 同时整除\n", big, small, divisor);
                    list.add(divisor);
                    big /= divisor;
                    small /= divisor;
                    // 能整除，那就先整除，然后继续下一轮试探。从2开始
                    divisor = 2;     // 重置为2
                } else {
                    // 不能同时整除，那就递增divisor，继续试
                    // System.out.printf("%s %s 不能被 %s 整除\n", big, small, divisor);
                    divisor++;
                }
            }
            list.add(big);
            list.add(small);
            return list;
        }
        
        /**
         * 判断数值big是否能被small整除。
         * @param big 较大的数
         * @param small 较小的数
         * @return 布尔值
         */
        static boolean canExactDivision(int big, int small) {
            int result = big / small;
            return (result * small) == big;
        }
    }