试题 算法训练 最大最小公倍数

试题 算法训练 最大最小公倍数

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

输入格式
输入一个正整数N。

输出格式
输出一个整数，表示你找到的最小公倍数。
样例输入
9
样例输出
504
数据规模与约定
1 <= N <= 106。

算法分析：
1.求区间内三个数的最大的最小公倍数，需要满足三个数互为质数（三个数最小公倍数<=他们的乘积，而当三个数互为质数时，他们的最小公倍数就等于他们的乘积）；

而三个数互为质数有以下要求：
根据质数的概念，相邻的连续自然数互为质数，相邻的奇数互为质数；
1、n为偶数时：
1.1 3能整除n时 n与n-2不互为质数。所以需要将最小值替换（体现贪心的思想）即将（n-2）替换为n-3,而n-3与n都能被3整除，不是互为质数，所以替换n-1为n-3并不可以，此时选择将n替换为n-1,此时n-1,n-2,n-3互为质数，最小公倍数即为(n-1)(n-2)(n-3);
1.2 3不能整除n时，n与(n-2)不是互为质数，将(n-2)替换成(n-3)，此时最小公倍数即为n(n-1)(n-3)
2.n为奇数时：
n,n-1,n-2互为质数，最小公倍数即为n*(n-1)*(n-2);

package t17;

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		long n = scanner.nextInt();
		max(n);
	}
	
	public static void max(long n) {
		long res;
		if(n<=2) {
			res = n;
		} 
		if(n%2==1) {
			res = n*(n-1)*(n-2);
		} else {
			if(n%3!=0) {
				res = n*(n-1)*(n-3);
			} else {
				res = (n-1)*(n-2)*(n-3);
			}
		}
		System.out.println(res);
	}
}

参考自https://blog.csdn.net/qq_36403227/article/details/88677874