Using a long as ArrayList index in java

Question

I am writing this java program to find all the prime numbers up to num using the Sieve of Eratosthenes, but when I try to compile, it says I can't use a long var as an array index, and it expects an int var in its place. But I'll be working with large numbers, so I can't use int. What can I do?

import java.util.*;
import java.lang.*;

public class t3{
    public static void main(String[] args){
        long num = 100;

        //declaring list and filling it with numbers
        ArrayList<Long> numlist = new ArrayList<Long>();
        for(long x=2 ; x<num ; x++){
            numlist.add(new Long(x));
        }

        //sieve or eratosthenes
        for(long x=0 ; x<Math.sqrt(num) ; x++){
            for(long y=x+1 ; y<numlist.size() ; y++){
                if(numlist[y]%numlist[x] == 0){
                    numlist.remove(y);
                }
            }
        }

        //print list
        for(Object item : numlist){
            System.out.println((Long)item);
        }
    }
}

Answer 1

The Java specification limits arrays to at most Integer.MAX_VALUE elements. While a List may contain more elements (this is true for Collections in general), you can only add/get/remove/set them using an int index.

Assuming you have the memory for that many elements (very unlikely I think), you could write your own data structure consisting of "concatenated" arrays. The get() and set() methods would take a long index and figure out the corresponding array and int index within that array.

Also, I would suggest using booleans to represent the state of each number, instead of storing/removing each number explicitly. This would be better because (1) booleans take less space than longs, and (2) shifting elements (as done in ArrayList) during element removal can be expensive.

Answer 2

I'm not sure why your code would compile to begin with.

You're not supposed to use [] in an array list to access members. An arraylist is merely a list that is internally stored in an array. You have to use the list get operation (which would still be O(1)). Writing numlist[index] means that you have an array of objects in numlist. You cannot override the [] operation as in C++.

In addition, an int is 32 bits in Java. Having an array of length greater than 2^32 (so you would need long indices) is unlikely and I'm not even sure the specification allows it.