c - 算法或 c 代码实现以找到具有 n 个或更多除数的最小正整数

Question

找到具有给定或更多除数的最小整数的有效方法是什么？我天真地认为，找到从 2 开始的数字的除数。当然这不是最好的方法。有没有办法猜测接近答案的起点？可能是 n 与其可以具有的除数之间的某种关系。

score 3 · Accepted Answer

如果一个数的素数分解n是： n = p1^a * p2^b * p3^c那么除数的个数是(a + 1) * (b + 1) * (c + 1)。

这是解决方案的提示。

问题并不像看起来那么简单。

我发现有趣的定理和论文解决了这个问题：

score 0 · Accepted Answer

你有没有想过使用埃拉托色尼筛法的改编版来做到这一点？依次遍历可能的除数，并在适当的点将累积总数加 1。例如，当您达到 5 时，将 1 加到 5、10、15 的总数中……这样做不需要对代码进行很大的修改。

2 回答 2