Checking large int values if they are prime, BigInteger problems in Java

Question

I'm try to see if large numbers are prime or not, number whose length are 11. Here is the code I am using:

private static boolean isPrime(BigInteger eval_number){

        for(int i=2;i < eval_number.intValue();i++) {
            if(eval_number.intValue() % i==0)
                return false;
        }
        return true;

    }

Now the number I'm inspecting in the debugger is eval_number which equals 11235813213. However when I inspect the eval_number.intValue() in the debugger instead of the value being 11235813213 the value is -1649088675. How is this happening? Also what would be a better way in inspecting large numbers to see if they are prime?

"How is this happening?" It's called an overflow. When the variable type only stores x bytes and you need y bytes to store the value you want, where y > x. — Fabio, Aug 08 '15 at 12:07
I don't know java, but the problem might be with intValue, since it returns an int and usually ints have low maximum value — Fabio, Aug 08 '15 at 12:09
limit the upper bound to `sqrt(eval_number)` and only check for divisibility of numbers of the form `6k ± 1` http://stackoverflow.com/a/1801446/995714 http://stackoverflow.com/q/453793/995714 — phuclv, Aug 08 '15 at 13:46

score 3 · Accepted Answer · answered Aug 08 '15 at 12:25

The strange value is a result of an overflow. The number held by the BigInteger instance is greater than 2^31-1 (Integer.MAX_VALUE) thus it can't be represented by an int. For the primcheck: BigInteger provides isProbablePrime(int) and there are several other fast (more or less) algorithms that allow to check whether a number is a primnumber with a given failure-rate. If you prefer 100% certainty you can optimize your code by reducing the upper-bounds for numbers to check to sqrt(input) and increasing the step-size by two. Or generate a prim-table, if the algorithm is used several times.

shot for that isProbablePrime function. – user481610 Aug 08 '15 at 12:52 — user481610, Aug 08 '15 at 12:52

score 2 · Answer 2 · edited May 23 '17 at 12:30

intValue() returns an integer equivalent for the given BigInteger number.

Since you are passing the value 11235813213, which is much larger than Integer.MAX_VALUE(maximum possible value for an int variable), which is 2147483647. So , it resulted in overflowing of the integer.

Also what would be a better way in inspecting large numbers to see if they are prime?

You should use only BigInteger numbers for finding out large primes. Also, check this question (Determining if a BigInteger is Prime in Java) which I asked a year ago.

Anonymous Coward · Answer 3 · 2015-08-08T13:24:53.757

As others have said the number you are checking is ouside of the range of int.
You could use a long, but that only delays the problem, it will still fail on numbers beyond long's range.
The solution is to use BigInteger arithmetic :

private static boolean isPrime(BigInteger eval_number) {
    for (BigInteger i = BigInteger.valueOf(2); i.compareTo(eval_number) < 0; i = i.add(BigInteger.ONE)) {
        if (eval_number.mod(i).equals(BigInteger.ZERO)) {
            return false;
        }
    }
    return true;
}

That is just a correction of the inmediate problem your question is about. There are still things to improve there. Checking for being prime can be made more efficient. You don't have to check even numbers except 2 and you only need to check till the square root of the number in question.

You might want to use `BigInteger.valueOf(2)`, to use a cached instance. — Tom, Aug 08 '15 at 12:29

score 1 · Answer 4 · answered Aug 08 '15 at 12:11

1

You convert BigInteger to 32bit integer. If it is bigger than 2^31, it will return incorrect value. You need to do all the operations over BigInteger instances. I assume that you use BigInteger because of long being insufficient for other cases, but for number you stated as an example would be use of long instead of int sufficient. (long will be enough for numbers up to 2^63).

answered Aug 08 '15 at 12:11

Vojtěch Kaiser

568
3
15

Just what I was going to say. – Roy Shahaf Aug 08 '15 at 12:16

score 0 · Answer 5 · answered Aug 08 '15 at 12:23

You have to make all operations with BigInteger, without converting it to int :

private static boolean isPrime(BigInteger eval_number) {
    for (BigInteger i = BigInteger.valueOf(2); i.compareTo(eval_number) < 0; i = i.add(BigInteger.ONE)) {
        if (eval_number.divideAndRemainder(i)[1].equals(BigInteger.ZERO)) {
            System.out.println(i);
            return false;
        }

    }
    return true;
}

score 0 · Answer 6 · edited Jul 21 '17 at 07:47

0

If you want to check whether a BigInteger is Prime or not you can use java.math.BigInteger.isProbablePrime(int certainty) it will returns true if this BigInteger is probably prime, false if it's definitely composite. If certainty is ≤ 0, true is returned.

edited Jul 21 '17 at 07:47

Rohit Poudel

1,793
2
20
24

answered Jul 21 '17 at 06:15

Manish Kr Jha

1
2

Checking large int values if they are prime, BigInteger problems in Java

6 Answers6