Error on finding larger primes

Question

I made a simple sieve of erastothenes program to calculate the sum of primes up to n for project euler. It works fine for 100, 1,000 , 10,000 and so on but when i do 1 or 2 million, it gives me this :

java.lang.ArrayIndexOutOfBoundsException: -2146737495

It doesn't happen for smaller numbers, i use boolean arrays.

boolean[] primes = new boolean[2000001];
    ArrayList<Integer> list = new ArrayList<Integer>();
    for (int i = 2; i < primes.length; i++){
        primes[i] = true;
    }
    boolean stop = false;
    int target = 2;
    int cycles = 1;
    while (!stop) {
        list.add(target);
        for (int i = target;; i ++) //
        {
            if (target*i >= primes.length ) {//
                break;
            }
            primes[target*i] = false;//

        }
        for (int i = target + 1; ; i ++) {

            if(i >= primes.length) {
                stop = true;
                break;
            }
             else if (primes[i]) {
                target = i;
                break;
            }
        }
        cycles ++;
    }
    int sum = 0;
        for (int i = 0; i < list.size(); i++) {
        sum += list.get(i);;
    }

My goal is not at all really to find the answer, but many times I have abandoned my code due to these types of errors. I'd like to find a source for them.

http://stackoverflow.com/questions/3001836/how-does-java-handle-integer-underflows-and-overflows-and-how-would-you-check-fo — assylias, Feb 08 '17 at 15:34
At what line does it crash? Have you tried debugging your code? — luk2302, Feb 08 '17 at 15:34
Also note that this `for (int i = target;; i ++) { if (target*i >= primes.length ) { break; } ... }` can be replaced by `for (int i = target; target*i < primes.length; i ++) { ... }` — assylias, Feb 08 '17 at 15:36
46349 * 46349 = 2,148,229,801 and the maximum supported `int` is 2,147,483,647, wraps over and becomes negative number. — Compass, Feb 08 '17 at 15:47
Possible duplicate of [How does Java handle integer underflows and overflows and how would you check for it?](http://stackoverflow.com/questions/3001836/how-does-java-handle-integer-underflows-and-overflows-and-how-would-you-check-fo) — giusti, Feb 08 '17 at 18:14

score 2 · Answer 1 · answered Feb 08 '17 at 15:53

You have a faulty check that doesn't take integer overflow into account.

for (int i = target;; i ++) //
{
    if (target*i >= primes.length ) {// This is the check
        break;
    }
    primes[target*i] = false;// Here is where it overflows

}

Once you hit an i that makes target * i larger than an integer can hold, the integer overflows. This means that now it will become negative. And of course, for a negative number, target*i >= primes.length will be false.

And of course, a negative number cannot be an index in an array. It should have stopped at the break, but it didn't because the condition was not met.

What you should do is calculate the maximum i that is allowed, and put that as the loop condition:

int maxI = primes.length / target;
for (int i = target; i < maxI; i ++) //
{
    primes[target*i] = false;// Here is where it overflows
}

The maxI is the maximum number that you can multiply by target and still not reach the primes.length. Now you don't need your check anymore (because multiplying target by i will never yield a number greater than primes.length. And it will also never overflow, as the multiplication always yields a number that is less than the size of the array, hence less than Integer.MAX_VALUE.

Another, less expensive (less multiplications) method would be:

if ( primes.length / target >= target ) {
    for (int i = target * target; i < primes.length; i += target ) //
    {
        primes[i] = false;
    }
}

The check in the if is necessary to avoid overflow in case you have a huge target.

score 0 · Answer 2 · answered Feb 08 '17 at 15:37

0

That's because you are using an int, which has an upper limit of 2^31-1: see https://en.wikibooks.org/wiki/Java_Programming/Primitive_Types

To handle big numbers, you should use the BigInteger class.

answered Feb 08 '17 at 15:37

Migwel

145
9

4

Note that then you wouldn't be able to use an array, as the indexes to an array are always integers. – RealSkeptic Feb 08 '17 at 15:37

score 0 · Answer 3 · answered Feb 08 '17 at 15:43

0

You have a problem with you primes array.

First of all, by reading the error, your array is clearly not 'long' enough for your logic, since you define it as boolean[] primes = new boolean[2000001]; and you have an ArrayIndexOutOfBoundsException of -2146737495.

So try to use a long or a BigInteger instead of a int for the variables i, target and cycles. Even so, you will have to rethink about your logic since the problem is not the overflow by itself, but the array that is not long enough.

answered Feb 08 '17 at 15:43

JFPicard

5,029
3
19
43

The array is long enough. The check that is supposed to ensure that you do not go outside of the array is faulty. – RealSkeptic Feb 08 '17 at 15:45
The logic is faulty IMHO, so I think that the solution is not checking if the index is out of the array, but to change how to find larger primes. – JFPicard Feb 08 '17 at 15:55

Error on finding larger primes

3 Answers3