最大公约数和最小公倍数

我不是女神ヾ 2022-05-13 01:50 211阅读 0赞

最大公约数我们要考虑这种情况，48 和 24 这种情况，48是24的二倍，我们仔细观察的话会发现，如果不是这种特殊情况，其它的情况就是，两个数最大的公约数也不会超过那个最小数的一半，所以我们锁定范围来遍历就行了，ok，找到就行了  
关于最大公约数这个算法呐，我找到了我们的离散老师和数学老师进行讨论，因为这个算法是我自己想出来的，我不知道对不对？所以比较谨慎，老师就是老师，老师说了一句话，让我坚定不移的认为我这个算法是对的：就是两个数中较小的那个数（除了1），它的除了（它本身的）最大公约数一定小于它自己的一半，所以说，这个算法成立。  
**最大公约数：**

import java.util.Scanner;
    
    /**
     * @ProjectName: BS
     * @Package: 春招.sample
     * @ClassName: 最大公约数
     * @Description: java类作用描述
     * @Author: alj
     * @CreateDate: 2018/9/9 16:54
     * @UpdateUser: 更新者
     * @UpdateDate: 2018/9/9 16:54
     * @UpdateRemark: 更新说明
     * @Version: 1.0
     */
    public class 最大公约数 {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int numberA = scanner.nextInt();
            int numberB = scanner.nextInt();
            int b = Math.max(numberA,numberB);
            int a = Math.min(numberA,numberB);
                if (b % a == 0) {
                    System.out.println(a);
                    return;
                }
                int c =a/2;
                for (int i =c ; i > 0 ; i--) {
                    if (b % i == 0 && a % i == 0) {
                        System.out.println(i);
                        return;
                    }
                }
        }
    }

**最小公倍数：**  
最小公倍数呐，  
这个算法呐，就是说，一定是那个最大的数的几倍，所以每次乘以它的倍数就行了。

import java.util.Scanner;
    
    /**
     * @ProjectName: BS
     * @Package: 春招.sample
     * @ClassName: 最小公倍数
     * @Description: java类作用描述
     * @Author: alj
     * @CreateDate: 2018/9/9 17:32
     * @UpdateUser: 更新者
     * @UpdateDate: 2018/9/9 17:32
     * @UpdateRemark: 更新说明
     * @Version: 1.0
     */
    public class 最小公倍数 {
        public static void main(String[] args) {
             Scanner scanner = new Scanner(System.in);
            int numberA = scanner.nextInt();
            int numberB = scanner.nextInt();
            int a = numberA > numberB ? numberA:numberB;
            int b = numberA < numberB ? numberA:numberB;
            int max = a*b;
            int j = 1;
            for (int i = a; i <=max ; i*=j) {
                if (i % a == 0 && i % b == 0) {
                    System.out.println(i);
                    return;
                }
                i = a;
                j++;
            }
        }
    }

今天的感悟呐，只有自己思考出来的东西才是印象最深的，才是属于自己。抄别人的，问别人啊，看别人的，没用的，下次见了还是不会的。