来个简单的，求n以内因数最多的数

liangbch

找出一个数x,使得x<=n 且 x的因数的个数为达到最多。 类似的问题可用穷举法和构造法。但对于这个问题，穷举复杂度很高，不予考虑。下面我们主要考虑构造法。 若$P_1$表示第一个素数（2），$P_n$表示第n个素数。我们容易推出n以内因数个数最大值的一个下限。 若 $P_1*P_2*...*P_k<=n$ 且 $P_1 * P_2* ... * P_(k+1)>n$，则p以内所有的数中，一定存在一个数，他的因子的个数 大于等于$2^k$. 我们先以 $n=2^64-1$ 为例，编写一个程序，构造1个数组 a[1..k]， 使得$P_1^{a[1]}*P_2^{a[2]}*...P_k^{a[k]}<=n$, 且$(a[1]+1)*(a[2]+1)*( a[k]+1)$ 取到最大值。

无心人

这个问题用对数做最好了

无心人

回家的路上想了 这个问题这么描述比较容易些 对数字k，求因子个数恰好是k的最小整数 另外，必须规定1作为因子参与计数 1不参与的可转换到这个问题 显然k是素数时， 最小n = 2^(k-1) k = p * r, p、r是素数，p <= r, n = 2^(r-1)*3^(p-1) 当k为高度复合数时，问题将变得比较复杂 和自然数的拆分，对数，不等式的最大值都将发生联系

无心人

k = 1, n = 1 k = 2, n = 2 k = 3, n = 4 k = 4, n = 6 k = 5, n = 16 k = 6, n = 12 k = 7, n = 64 k = 8, n = 24 k = 9, n = 36 k = 10, n = 2^4*3 = 48 以下素数、p*q, p^2情况略 k = 12, n = 2^2*3*5 = 60 k = 16, n = 2^3*3^3 = 216 k = 18, n = 2^2*3^2*5= 180 k = 20, n = 2^4*3*5 = 240 k = 24, n = 2^3*3^2*5 = 360 k = 27, n = 2^2*3^2*5^2 = 900 k = 28, n = 2^6*3*5 = 960 k = 30, n = 2^4*3^2*5 = 720 k = 32, n = 2^3*3*5*7 = 840 k = 36, n = 2^2*3^2*5*7 = 1260 k = 40, n = 2^4*3^3*5 = 2160

medie2005

$\prod_{i=1}P_{i}^{c_{i}}$$<=N$ （1） $max{\prod_{i=1}(c_{i}+1)}$ （2） 对（1）取对数，得： $\sum_{i=1}{c_{i}*log(p_{i})}<=log(N)$ (3) 记$\sum_{i=1}{log(P_{i})}=S$ 则（3）式可变为： $\sum_{i=1}{(c_{i}+1)*log(p_{i})}<=log(N)-S$ (4) 记$x_{i}=c_{i}+1$, $k_{i}=log(P_{i})$，则问题变成了： $\sum_{i=1}{k_{i}*x_{i}}<=log(N)-S$ $max(\prod_{i=1}{x_{i}})$ 因此，我们只要使$k_{i}*x_{i}$尽量平均就可以了。

无心人

k = 48， n = 2^3*3^2*5*7 = 2520 k = 50, n = 2^5*3^4*5 = 6480 k = 54, n = 2^2*3^2*5^2*7 = 6300 k = 56, n = 2^6*3*5*7 = 6720 k = 60, n = 2^4*3^2*5*7 = 5040

无心人

使用haskell找 题目对应的数字的 有4个不同素因子的 最多的要过9000的 Prelude> let c2 = floor(64 * log(2) / log(2)) Prelude> c2 64 Prelude> let c3 = floor(64 * log(2) / log(3)) Prelude> let c5 = floor(64 * log(2) / log(5)) Prelude> let c7 = floor(64 * log(2) / log(7)) Prelude> let a4 = [(s, a, b, c, d) | a <-[1..c2], b <- [1..c3], c <- [1..c5], d <- [1..c7], 2^a * 3^b * 5^c * 7^d < 2^64, let s = (a+1)*(b+1)*(c+1)*(d+1)] Prelude> let sss x = filter (\(s, a, b, c, d) -> s > x) a4 [(9856,15,10,7,6),(9792,16,11,7,5),(9720,17,9,8,5),(9702,17,10,6,6),(9828,17,12, 6,5),(9702,20,10,6,5)] 最多的是2^15*3^10*5^7*7^6 9856个因子

无心人

同样道理 5个因子的21000，两组解， 第二个小 [(21000,13,9,5,4,4),(21000,14,9,6,4,3)] 6个因子的，37800 [(37800,13,8,4,4,3,2) 7个因子的，58320 [(58320,11,8,4,3,2,2,2)

无心人

8个的手工得到的一个 70560 Prelude> let b = 2^6*3^6*5^4*7^3*11^3*13^2*17^2*19 Prelude> b - 2^64 -6093021520417431616 Prelude> 7*7*5*4*4*3*3*2 70560 用C程序得到 最大结果 83160 10 6 4 3 2 2 2 1

无心人

9个因子的，手算得到一个 Prelude> let d = 2^6*3^6*5^4*7^3*11^3*13^2*17*19*23 Prelude> d - 2^64 -1732884148667271616 Prelude> 7 * 7 * 5 * 4 * 4 * 3 * 2 * 2 * 2 94080 用缩小范围的C程序得到9最大的结果 103680 7 5 4 3 2 2 2 1 1