java - 有没有另一种算法来实现这个功能(求理想整数的个数。)

Question

找出给定段 [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;
}

Answer 1

我继续解决这个问题。这是我想出的解决方案，但是我不能保证它对所有可能的值都能正常工作；)。

喜欢 @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 有点挣扎返回 -Infinity ，所以如果 a 我只是返回 0 而不是最终是 0因为精度不够。

如果在 min 范围内没有有效的理想数可能大于 max .我想知道这是否可以用于提前终止，但我想它可以忽略不计。