最大最小公倍数

问题

描述

已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。

思路

贪心思路，首先求最小公倍数中的最大的数，所以要从最大的数N开始考虑，因为相邻的两个奇数的最大公约数是1；并且相邻两个奇数之间的偶数与这两个奇数的最大公约数是1；所以要分N是奇数还是偶数，并且当N是偶数时还要讨论是否可以被3整除。

Code

public class biggest_lcm {
    public static void main(String[] args) {
        Scanner as=new Scanner(System.in);
        long n=as.nextLong();
        long r=0;
        if(n%2==1) {
            r=n*(n-1)*(n-2);
        }else {
            if(n%3!=0) {
                r=n*(n-1)*(n-3);
            }else {
                r=(n-1)*(n-2)*(n-3);
            }
        }
        System.out.println(r);
    }
}

解析

• 当N是奇数时，结果r就为N*（N-1）(N-2)；当N为偶数时，讨论N是否可以被3整除，当N不可以被3整出时，r=N(N-1)*(N-3)；
• 当N可以被3整除时N与N-3存在公约数3所以公式不是最大最小公倍数，r应当为N*(N-1)(N-4)或者(N-1)(N-2)(N-3),数学公式求得(N-1)(N-2)(N-3)>N*(N-1)(N-4)，(N>=3)，所以r=(N-1)(N-2)(N-3)。