对于任意输入的在3-100之间的正整数n,请编程求出具有n个不同因数的最小合数

Question

如题所述

Answer 1

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

1): n=p1^c1*p2^c2*...*pk^ck的因子个数是(1+c1)*(1+c2)*...*(1+ck).
2): 若具有n个因子的最小自然数是m=p1^c1*p2^c2*...*pi^ci,那么我们有:
a): c1>=c2>=c3>=...>=ci;
b): p1,p2,p3,...,pi是从2开始的连续素数;
c): (1+c1)*(1+c2)*...*(1+ci)=n.
上面的a)和b)是解决这个问题的关键,证明不难,你自己可以证明.
于是,剩下的问题只是分解n,然后,分配指数,对每种分配方案计算得到的结果,从中找到最小的就行了,当然这个可以用回溯法来做,中间可以加一些剪枝.

“”恰好有N个因子的最小正整数M“”

“”  u014046022 82424685“”

有了上面的定理之后，要求解m，转化为求解 n=f(x) 即 求解n=(a1+1)(a2+1)⋯(ak+1) 使得 p1^a1⋅p2^a2⋯pk^ak最小。这里显然以越大的质数为底的指数应该尽可能的小，也就是指数应该满足ai≥ai+1ai≥ai+1, 于是我们就可以通过搜索来求解这个问题了。

其中a1>= a2>=a3...>=ak

p1=2,p2=3,p3=5,p4=7  质数序列。

Answer 2

一个知识：一个数，分解为质因数p1,p2，……，pk
每个质因数的指数分别为
j1,j2，……，jk
在组成因数时，取各个质因数的若干个的积，每个质因数，可以不取(0个，按1计算)，或1个，最多ji个，共(ji十1)种情况。根据乘法原理，不同的因数个数(j1十1)(j2十1)……(jk十1)
比如，4=2＾2，不同的因数个数2十1=3个,1,2,4。
36=2＾2×3＾2,不同的因数个数(2十1)(2十1)=9个：1,2,3,4,6,9,12,18,36.
如此可知，n=100，最小的合数是2＾99。
对于n，最小合数是2＾(n-1)
计算2＾(n-1)即可。

Answer 3

要实现这个操作，需要用到以下数论知识，任意一个合数Q都可表示为若干个素数积，即：
Q=Πpₖ^mₖ （k=1,2,...,n)
那么Q的因子总数
N=(m₁+1)(m₂+1)...(mₙ+1)
比如合数250=5³2¹，其因子总数为(3+1)(1+1)=8个
那么反过来，如果已知一个合数Q因子总数为8，那么可以将8进行因数分解，比如8可以分解为以下3种形式：
8=1*8=(7+1)
8=2*4=(1+1)(3+1)
8=2*2*2=(1+1)(1+1)(1+1)
那么所有因子数为8的合数可以写为以下3种形式：
Q=p⁷
Q=p₁¹p₂³
Q=p₁¹p₂¹p₃¹
当p取最小值时，Q就最小，显然这3种形式的最小值分别是2⁷、2³3¹、2¹3¹5¹
其中最小的是中间一种结果为24。
编程思路：
1、输入n
2、将n分解为m个素因数（包含相同素数）
3、将m个素因数分别分成1、2，...，m组
得到各组对应的素因数指数，从大到小排序
4、代入最小的素数得到各组最小合数
5、找出各组最小合数