找到具有最大除数的1到100范围内的数字

Question

如何找到除数最多的1到100范围内的最小数字？我知道一个简单的方法是检查每个数字的除数从1到100并跟踪具有最大除数的数字.但是有更有效的方法吗？

Answer 1

有一种“更简单的方法”，但它是理论上的，而不是真正的计算机算法。出现两种不同的情况 - 一种情况是“大多数因素”就是您的意思，另一种情况是这些因素必须是唯一的。

在第一种情况下，您只需要认识到，为了最大化因子的数量，每个因子需要尽可能小，即 2。小于 100 的数最多，因此是 2 的最大幂不到 100，恰好是 64。

如果因子必须是唯一的，那么我们只需使用 2、3、5 等（质数），直到下一个累积乘积大于 100 - 在本例中，2*3*5=30 是具有最独特的因素。添加第四个因子将使其变为 210，因此这是我们可以达到的最高值。