java - 检查数字是否丑陋

Question

我正在做这个问题:

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

这是我的尝试:

public class Solution {
    public boolean isUgly(int num) {
        if (num == 1) {
            return true;
        }
        for (int i = 7; i <= num / 2; i++) {
            if (isPrimeFactor(i, num)) {
                return false;
            }
        }
        return true;
    }

    public boolean isPrimeFactor(int candidate, int num) {
        return isPrime(candidate) && isFactor(candidate, num);
    }

    public boolean isPrime(int num) {
        if (num == 2) {
            return true;
        }
        if (num % 2 == 0) {
            return false;
        }
        for (int i = 3; i <= Math.sqrt(num); i += 2) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    public boolean isFactor(int candidate, int num) {
        return (num % candidate == 0);
    }
}

不幸的是，它在测试输入 -2147483648 时失败。当它应该为 false 时它返回 true。

知道我做错了什么吗？

Answer 1

您只是忘记了以下强调的条件:

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

因此，您只需要在 isUgly 方法中添加一个负数检查:

if (num <= 0) {
    return false;
}

---

作为旁注，您也许可以通过交换 isPrimeFactor 中的条件并测试 isFactor(candidate, num) && isPrime(candidate) 来稍微提高性能而不是 isPrime(candidate) && isFactor(candidate, num)。这是因为确定一个数是否是另一个数的因数比确定一个数是否为质数更快。