java - 是否有另一种算法来实现此功能(查找理想整数的数量)。

在给定的段[low，high]内找到理想整数的数量。理想数字是只有3和5作为质数的正整数。理想数可以以3 ^ x * 5 ^ y的形式表示，其中x和y是非负整数。例如，15,45和75是理想数，而6,10,21不是理想数。

我认为这个算法是O（n * m）;

我们可以实现为O（n + m）

static long getIdealNums(long low, long high) {

    int count = 0; // counter

    for (long i = low; i <= high; i++) {
        long num = i;

        // While num is divisible by 3, divide it by 3
        while (num % 3 == 0)
            num /= 3;

        // While num is divisible by 5, divide it by 5
        while (num % 5 == 0)
            num /= 5;

        // If num got reduced to 1 then it has
        // only 3 and 5 as prime factors
        if (num == 1)
            count++;
    }

    return count;
}

最佳答案

我继续前进，对这个问题感到很开心。这是我想出的解决方案，但是我不能保证它对于所有可能的值都可以正常工作;）。

如@JoopEggen所述，它可以更快地迭代已知的理想数字。
在下面的示例中，我尝试找出固定值x的有效范围y。

public static double logb(double a, double b) {
    return (a == 0) ? 0 : Math.log(a) / Math.log(b);
}

public static int getIdealNums(long low, long high) {

    int y = 0;

    int maxY = (int) Math.floor(logb(high, 5));
    int count = 0;

    do {
        long exp = (long) Math.pow(5, y);

        int min = (int) Math.ceil(logb(low / exp, 3));
        int max = (int) Math.floor(logb(high / exp, 3));

        if (min <= max) {
            count += max-min+1;
        }

    } while (++y <= maxY);

    return count;
}

我在Math.log return -Infinity上有些挣扎，所以如果a由于缺乏精度而最终成为0，我只是返回0。

如果没有有效的理想数字，则min可能大于max。我想知道这是否可以用于提早终止，但我认为它可以忽略不计。