Java: Incorrect Output when Factoring

Question

I'm trying to write a function to determine whether a number is "ugly". For a number to be "ugly", it must have no prime factors other than 2, 3, or 5.

Here's my attempt:

public class Solution {

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

public boolean isUgly(int num) {
    if (num < 0) {
        num *= -1;
    }
    for (int i = 7; i <= Math.sqrt(num); i += 2) {
        if ((num % i == 0) && isPrime(num)) {
            return false;
        }
    }
    return true;
}

}

I'm getting true for input = -2147483648 when it should be false. Is it possible there's an overflow here? I've gone over my code and the logic looks right to me...

Thanks!

@RealSkeptic Just added in checks for this and I get the same issue. Looks like an overflow problem... — anon_swe, Aug 22 '15 at 14:13
@RealSkeptic Just turned it into a positive number if it's negative as it'll have the same factors. Source updated — anon_swe, Aug 22 '15 at 14:21
@PiyushVishwakarma from isUgly, that's what the tests are run against — anon_swe, Aug 22 '15 at 14:23
@bclayman a simple way to solve your problem is to add an exception for Integer.MIN_VALUE — , Aug 22 '15 at 14:32

score 3 · Answer 1 · 2015-08-22T14:33:59.627

3

The problem is Integer.MIN_VALUE*-1 = Integer.MIN_VALUE leading to Math.sqrt(Integer.MIN_VALUE) which returns NaN on a negative number, so then when you perform this operation 7 <= Math.sqrt(Integer.MIN_VALUE) it returns false and doesn't even enter the for loop resulting in the program returning true.

I hope this explanation helps.

edited Aug 22 '15 at 14:33

answered Aug 22 '15 at 14:16

score 1 · Answer 2 · answered Aug 22 '15 at 14:08

Yeah, I guess so.

Java lower limit for int is -2147483648 and upper 2147483647. As shown in

public class MainClass {

  public static void main(String[] arg) {
    System.out.println(Integer.MAX_VALUE);   

    System.out.println(Integer.MIN_VALUE);   

  }
}

score 0 · Answer 3 · edited Jun 20 '20 at 09:12

Negative numbers are tricky in such a question.

You have to take the absolute number and factor it. In your original source, you didn't do this. It meant that you got a NaN from the Math.sqrt method. Which also meant that you got false when you compared it to 7.

So your original method would have returned true for all negative numbers.

But changing the sign (which, by the way can be done by num = -num rather than multiplication), which would solve it for all negative numbers, actually introduced an overflow into the program.

The number -2147483648 is, in fact, -2³¹. The maximum positive number allowed in an int is 2³¹-1. So the number - Integer.MIN_VALUE always overflows... into itself. It remains negative after you negate it!

So you run into that NaN again.

But note - since the number is -2³¹, it doesn't, in fact, have any other prime factors other than 2. So the method really should return true for it - assuming that you are not considering -1 a prime.

So I believe that your expectation that it should be false is incorrect - but it depends on the assignment's definition of the prime factors of negative numbers.

Notes:

Your program checks isPrime(num) instead of isPrime(i), and therefore it will always return true. num cannot both be divisible by i and be prime at the same time.
Limiting your program to the square root of num is wrong to begin with. For example, take the number 881305274. Its prime factors are 2 and 440652637. But 440652637 is much bigger than sqrt(881305274). The square root trick works for prime testing, because any factor that is bigger than the root has to be multiplied by a factor that's smaller than the root. But this doesn't apply to the "ugly" problem.

Also, prime numbers are not considered "ugly" as they are a factor of themselves. But your program, because it limits itself to the square root, will never return false for prime numbers.

Java: Incorrect Output when Factoring

3 Answers3