BitSet(JAVA) is throwing outofBoundsException in the implementation of Sieve Of Eratosthenes

Question

Here is my function for the implementation of Sieve Of Eratosthenes,

void solve() throws IOException {

    int n = 200000;

    ArrayList<Integer> primes = new ArrayList<Integer>();
    BitSet bs = new BitSet(n + 1);

    for(int i = 0; i <= n + 1; i++)
        bs.set(i);

    //setting bits at 0 and 1 to 0, since these are not considered as primes
    bs.clear(0);
    bs.clear(1);

    for(int i = 2; i <= n + 1; i++) {
        if(bs.get(i)) {
            //cross out multiples of i starting from i*i (lesser one would have always been crossed out)
            for(int j = i*i; j <= n + 1; j += i)
                {
                    bs.clear(j);
                }

            primes.add(i);          //add this prime to the list

        }
    }

    for(int e : primes)
        out.println(e);
}

When I run this I get and arrayOutOfBoundsException during the inner for loop, i.e.

for(int j = i*i; j <= n + 1; j += i)
{
  bs.clear(j);            //EXCEPTION is raised here
}

Error Message that I am getting is:

Exception in thread "main" java.lang.IndexOutOfBoundsException: bitIndex < 0: -2146737495
at java.util.BitSet.clear(BitSet.java:532)
at ERATOSTHENES.solve(ERATOSTHENES.java:45)

I dont understand where is the problem, if I reduce n to 20000, then my code works fine, but after n = 168000 (approx.), it shows this OutofBoundsException.

Is it something specific to BitSet, some property that I am not getting?

Answer 1

You are initialising (in the worst case) the variable i to be a large number close to 200,000 (specifically a large prime number?). That means j, which is initialised as i * i, will be in excess of 40,000,000,000, which is significantly over the max value of int (approx. 2,147,000,000) That means they will overflow over to negative values, which will definitely be out of range.

To solve the problem in this case, declare your variables to be of type long which is 64-bit and can hold much larger values.

Answer 2

You are getting an integer overflow in this line (i*i is negative):

for(int j = i*i; j <= n + 1; j += i)

Example:

System.out.println(168000 * 168000);

Prints:

-1840771072

Which is negative, so is less than n + 1 and passes cycle condition.

Answer 3

I think it could be because you are using an int and the number is getting too big i.e.

200,000 * 200,000 is a huge number and should probably be a long instead.