算法训练之最大最小公倍数 ALGO002
问题描述
已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。
输入格式
输入一个正整数N。
输出格式
输出一个整数，表示你找到的最小公倍数。
样例输入
9
样例输出
504
数据规模与约定
1 <= N <= 106
当看到这个题目第一眼，想当然的以为会是N （N-1） (N-2)三者乘积，并且这个题目给出输入示例的9刚好输出示例的504符合这个想法，但仔细一想就会发现不对，比如当N = 6时，1~6的最小公倍数是3 * 4 * 5 =60，因此发现有数学知识涉及，不是简单的最后三个数相乘
这个题涉及到的数学知识：
(1)、当N为奇数时,那么N,N-1,N-2互为质数,很明显NN-1N-2是1~N最小公倍数的最大值。
(2)、当N为偶数时,且能被3整除时,N-1,N-2,N-3互质,此时（N-1）（N-2）（N-3）是1到N最小公倍数的最大值；当N为偶数时,但不能被3整除时,N,N-1,N-3互质,此时N*（N-1）*（N-3）是1~N最小公倍数的最大值。
好了，话不多说，我的源代码如下：
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); long []array = new long[N]; for (int i = 0; i < N; i++) { array[i] = i + 1; } long m = 0 ; if (N % 2 == 1) { m = array[N-3] * array[N-2] * array[N-1]; }else { if (N % 3 == 0) { m = array[N-4] * array[N-3] * array[N-2]; }else { m = array[N-4] * array[N-2] * array[N-1]; } } System.out.println(m); scanner.close(); } }
