对于任意输入的正整数n,请编程求出具有n个不同因子的最小正整数m。

对于任意输入的正整数n,请编程求出具有n个不同因子的最小正整数m。
    例如：n=4，则m=6，因为6具有4个不同整数因子1，2，3，6；而且是最小的有4个因子的整数。

5 个解决方案

#1

补充：n<=50000

#2

我说一种方法（可是有点不现实:-))
首先拥有一个素数表。
当你给出一个n（n>3)，在表中从小到大找出n-2个素数，将这些素数乘起来，就是结果。

#3

由于
p1^a1 * p2^a2 *...*pt^at
因子的个数为(a1+1)(a2+1)...(at+1)
首先可以对n进行因子分解，如果n是素数，那么没有法子，结果就是2^(n-1).
不然，就需要试验n的各种不同的乘积方案，
比如n=8,分解方案有
8=8 ,对应 2^7  =128
8=4*2, 对应 2^3 * 3^1 = 24.
8=2*2*2,对应2*3*5=30.
所以最小的数为24。

由于n的因子不会很多(n<=50000),穷举已经很简单了）

#4

把n分解因式
设n=2^a1*3^a2*5^a3*7^a4*......
则n的所有因数的个数为(a1+1)*(a2+1)*(a3+1)*(a4+1)*.....
[比如24=2^3*3^1,则24的因数个数为(3+1)*(1+1)=8]
所以主要就是求出a1,a2,a3,a4...
unsigned long evaluate(unsigned long n)
{
  unsigned long i,j,m=1;
  for (i=2;i<=n/2;i++){
    for (j=2;j<=i/2;j++) if (i%j==0) break;
    if (j>i/2&&n%i==0) m*=(n/i+1);
  }
  return m;
}

#5

然后:
  unsigned long i;
  for (for i=0;i<50000;i++) if (evaluate(i)==m) break;
  if (i<50000) ....;//successful,the value equals i;
  else //failed,can not find matched i that less than 50000;