algorithm - 找出恰好有 N 个因数的最小数

Question

假设我们有 N 个除数。我想找到一个有 N 个除数的最小数。

我的算法

• 我找到了素数(pm = [2,3,5,7,..])
• 我找到了 N 的质因数(N=12, p=[2,2,3], reverse p rp = [3, 2, 2])
• number *= pm[i]^(rp[i]-1), i = 1...素因子的长度

对于 N=12，答案是 60 = 2^(3-1) * 3^(2-1) * 5^(2-1)

但是对于数字 243，我的算法给出了错误的答案(5336100 - 但它不是具有 243 个除数的最小数字)。预期数量是 2822400。

我错在哪里？有文献吗？

Answer 1

让我们从 OEIS sequence 开始.现在任何数字都可以表示为素数幂的乘积。

How many divisors会有吗？您可以使用组合数学证明它将具有:

因此，您必须求解上面的表达式等于您拥有的除法数的方程式。我不会在这里编写代码，但请注意，因为您正在寻找整数解决方案，所以您可以分解出您的除数。

当您找到m_i 时，您可以通过对m_i 进行排序并将最大的m_i 分配给最小的素数来获得最小的数。因此，如果您的 m1 = 2、m2 = 5、m3 = 2，则数字将为 2^5 * 3^2 * 5^2.