求分解后x的最小公倍数

简介:
import java.math.BigInteger;
import java.util.*;

public class Hello
{
	 static final int N = 1005;
	 static boolean prime[] = new boolean[N];
	 static int p[] = new int[N];
	 static BigInteger dp[][] = new BigInteger[N][N];
	 static BigInteger ans[] = new BigInteger[N];
	 static int k;
	 
	 static void isprime()
	 {
		  k = 1;
		  int i,j;
		  Arrays.fill(prime,true);
		  for(i=2;i<N;i++)
		  {
			   if(prime[i])
			   {
				    p[k++] = i;
				    for(j=i+i;j<N;j+=i)
				    {
				    	 prime[j] = false;
				    }
			   }
		  }
	 }
	 
	 static BigInteger max(BigInteger a,BigInteger b)
	 {
		  if(a.compareTo(b) == 1) return a;
		  else return b;
	 }
	 
	 static void Work()
	 {
		  for(int i=0;i<N;i++)
		      for(int j=0;j<k;j++)
		    	  dp[i][j] = BigInteger.ONE;
		  for(int i=1;i<k;i++)
			  dp[2][i] = BigInteger.valueOf(2);
		  for(int i=3;i<N;i++)
		  {
			   for(int j=1;j<k;j++)
			   {
				    dp[i][j] = dp[i][j-1];
				    int tmp = p[j];
				    while(i >= tmp)
				    {
				    	 dp[i][j] = max(dp[i][j],dp[i-tmp][j-1].multiply(BigInteger.valueOf(tmp)));
				    	 tmp *= p[j];
				    }
			   }
		  }
		  ans[0] = ans[1] = BigInteger.ONE;
          ans[2] = BigInteger.valueOf(2);
		  for(int i=3;i<N;i++)
		  {
			   ans[i] = BigInteger.ZERO;
			   for(int j=1;j<k;j++)
				    ans[i] = max(ans[i],dp[i][j]);
		  }
	 }
	 
	 public static void main(String[] args)
	 {
		  isprime();
		  Work();
		  Scanner cin = new Scanner(System.in);
		  while(cin.hasNext())
		  {
			   int n = cin.nextInt();
			   System.out.println(ans[n]);
		  }
	 }
}

目录
相关文章
|
6月前
|
算法 测试技术 C#
【数学】【数论】【最大公约数】1819. 序列中不同最大公约数的数目
【数学】【数论】【最大公约数】1819. 序列中不同最大公约数的数目
|
6月前
|
算法 Python
最小公倍数算法
最小公倍数算法
|
6月前
|
算法 Python
最大公约数算法
最大公约数算法
|
算法 C语言 C++
【数论】最大公约数、约数的个数与约数之和定理
先来科普下什么是约数:当a能被b整除,我们就说b为a的约数,b的倍数为a
113 0
求解最大公约数和最小公倍数
求解最大公约数和最小公倍数
求解最大公约数和最小公倍数
求解最大公约数(两种)
求解最大公约数(两种)
145 0
[解题报告]【第24题】给定 a 和 b,求它们的最小公倍数 | 最小公倍数 和 最大公约数有什么关系呢?
[解题报告]【第24题】给定 a 和 b,求它们的最小公倍数 | 最小公倍数 和 最大公约数有什么关系呢?