寻找一个具有恰好N个因数的最小数

Question

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

我的算法如下：

• 我找到了质数(pm = [2,3,5,7,..])
• 我找到了N的质因数(N=12, p=[2,2,3]，反转后的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。

我的错误在哪里？有没有相关文献可以参考？

- Isabek Tashiev

---

@SalvadorDali，如果你能给我关于这个任务的文章和文献，那就太棒了。我是指理论方面的。 - Isabek Tashiev

这个方法对于N = 3也无法成功吗？你的方法似乎得出了8，但是6不是正确答案吗？ - Heman Gandhi

@HemanGandhi，我的方法对于N = 3给出了4。2^(3-1) = 4。而且4是正确的答案。 - Isabek Tashiev

Answer 1

让我们从OEIS序列开始。现在任何数字都可以表示为质数的幂的乘积。 它将具有多少约数？你可以使用组合数学证明它将具有： 因此您必须解决等式，其中上面的表达式等于您拥有的分区数。我不会在这里编写代码，但请注意，因为您正在寻找整数解，所以您可以将约数个数分解出来。

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

- Salvador Dali

---

这个回答并不是很有帮助。您只是重新描述了 OP 已经在问题中提出的技术，正如他所说的，并不总是给出正确的答案。问题在于 m_i 的解决方案不是唯一的。请参阅 @user3386109 的答案以进行进一步分析。 - kfx

@kfx 我稍后会让它更有帮助一些。很抱歉它对你没有帮助。 - Salvador Dali

Answer 2

在SalvadorDali的回答基础上:

既然N是(m_i+1)的乘积，你尝试通过计算N的质因数分解，然后从每个因子中减去1来找到m_i。

但这并不一定给出最小的答案，就像你举的N=243的例子一样。243的质因数分解为

243 = 3*3*3*3*3

你的方法建议最小值应该是：

2^2 * 3^2 * 5^2 * 7^2 * 11^2 = 5336100

然而，243的备选复合因式分解是：

243 = 9*3*3*3

这句话的意思是建议设置一个最小值。

2^8 * 3^2 * 5^2 * 7^2 = 2822400

复合因式分解效果更好，因为2的6次方小于11的平方。所以一般来说，您的方法只是一个起点。在计算出答案后，您需要将最大的质数折叠到最小的质数中，以改善答案。

- user3386109