Why does 2147483647 is the only Int that the code I wrote does'nt get the right feedback?

Question

I wrote a code that finds if a number is prime or not. for every prime number it prints the number + is prime for every number that isn't prime it prints the number=the lowest divider*the highest divider

only for the biggest int (2147483647) it prints the second line all though it is a prime number... why so?

the code:

import java.util.Scanner;
public class FindDivisors2meth {
    public static void main(String[] args) {
        Scanner myScanner = new Scanner(System.in);
        int n = myScanner.nextInt();
        boolean isPrime = true;
        int p = 2;
        while( p * p <= n & isPrime ) {
            if( n % p == 0) {
                isPrime = false;
            }
            else {
                p = p + 1;
            }
        }
        if( isPrime) {
            System.out.println(n + " is prime");
        }
        else {
            System.out.println(n + "=" + p + "*" + n/p);
        }
    }

}

Answer 1

When you try to input 2147483647, your program is treating it as an int, and due to the limitations of the data type, it overflows, causing unexpected behavior. You can try this 'Long' instead of 'int', it shall return 2147483647 is prime. :)

Answer 2

Your issue is number overflow. Your numbers occupy a finite number of bits. A java int is of 32 bits, that is, the biggest number is 2^32 - 1, because we need half of the space to represent negatives.

Now, you are incrementing a number until its square is smaller or equal than your input and isPrime is false. But, if your input happens to be 2^32 - 1, then the first criteria will never be true. Hence, you will eventually have p overflowing the int boundaries and slowly but surely incrementing it until it's 1 and then your algorithm will claim it's not a prime. Instead of this, compute the square root of your input and use that as the limit of your loop and then it will work.

Answer 3

2147483647 is the largest number that possibly fits in an int. You see, int does not mean 'any integral number'. It actually means: an integral number that fits in 32-bits - treating it as a signed (represented with 2's complement) number.

The upshot is, 2^31-1 is the largest positive number that 'fits', and -2^31 is the largest negative number that 'fits'. These numbers wrap around:

int x = 2147483647;
System.out.println(x == Integer.MAX_VALUE); // true
x++;
System.out.println(x); // -2147483648
System.out.println(x == Integer.MIN_VALUE); // true
x--;
System.out.println(x); // 2147483647

Crucially, then, p * p <= n can not ever be false, because n is the largest possible int, and therefore, no number can be larger than it. Hence your while loop runs forever, and, eventually, after a very large amount of loops, the value of p hits 2147483647. At which point you loop one more time, and now p is -2147483648. You keep looping a lot more and eventually (after 4294967293 times, in fact!), p ends up being 1, and now finally n % p is indeed 0, so, isPrime is set to false and that's how your loop ends - the only way it can, by isPrime being false, given that p * p <= n can't be false (X <= n for any X where n is the maximum int value can never be false, think about it. How can a number not be 'less than or equal' to the largest number in existence)?

Solutions

1. Use long instead. This buys you a bit of space; longs are 64-bit but otherwise identical, and therefore go up to 2^63-1 and down to -2^63, i.e. about 18 digits worth. You'll still have an issue if someone enters exactly 2^63-1, unless.. you continue to use .nextInt(), but assign it to a long. Now you don't have that problem!

2. Special-case it. The real problem here is that p*p becomes negative (because any result above 2^31-1 'loops around'), so, find that value for which that would be true (it's any number larger than SQRT(2147483647) - which you can just run on a calculator)) - you can stop if p is above that or if p*p is above n.

3. use BigInteger, now your code can handle any size input, though, it'll be incredibly slow compared to efficient prime-finders.