algorithm - 如何高效地统计[start,end]之间质因数只有3或5的数字？

Question

在编码评估中，我遇到了这个问题，其中运行时的超时限制为 10 秒。问题要求返回只能被 3 或 5 整除且不能被任何其他数字整除的数字的计数，我对如何有效地解决它感到有点困惑。

这基本上是我尝试过的:

count = 0
for num in start...end:
   while num % 3 == 0: num /= 3
   while num % 5 == 0: num /= 5
   if num == 1:
      count += 1

Answer 1

所有解的形式都是3^x * 5^y。我们将考虑每个y值的结果。我们首先找到具有有效结果的最大 y 值，然后查看 x 的哪些对应值产生高于 start 的最小乘积> 及以下 end。 x 的两个值之间的差值就是该 y 值的有效结果数。然后我们递减y并将乘积除以5，并检查是否可以通过增加x的值使乘积回到范围内。依此类推...即使对于大范围，这最多也需要几十次计算。

如果您想保持简单并坚持整数算术并避免对数等昂贵的运算，您可以这样做:
(它在常规整数范围的时间限制内舒适地计时，但我还没有尝试过使用大整数。)

function factors3and5(start, end) {
    var fives = 0;
    var threesMin = 0, threesMax = 0;
    var productMin = 1, productMax = 1;
    var count = 0;

    while (productMax < end) {
        ++fives;
        productMax *= 5;
    }
    productMin = productMax;

    while (fives-- > 0) {
        productMin /= 5;
        productMax /= 5;
        while (productMin <= start) {
            ++threesMin;
            productMin *= 3;
        }
        while (productMax * 3 < end) {
            ++threesMax;
            productMax *= 3;
        }
        count += threesMax - threesMin + 1;
    }
    return count;
}
document.write(factors3and5(12345, 111222333444555)); // 288