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

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.

Answer 2

A similar question.

Answer 3

Realize that with a 32-bit signed int index to a long[] you're addressing 16GB of RAM.

If you're really serious about getting to big primes with the sieve, you're not going to get away with several things in your current impl:

• ArrayList of boxed longs
• Using [] like Uri mentions
• Not systematically paging to disk

Answer 4

At least the theoretical maximum size of java arrays is Integer.MAX_VALUE. This is because the type of the array index is according to the spec an int. In reality it depends on your memory though.

So if your algorithm really depends on having such a large array you are out of luck with java arrays.

As I doubt you will need all the space you could write your own collection class that acts like a array but does not need as much memory. It would collapse the wholes in the address space (so to speak). Of course this might change the runtime behavior you are expecting from the algorithm.

Answer 5

The simple solution: considering that num is never larger than 100 in your code sample, just change it's type to int.

But the points others have mentioned about address space are also good points.

Answer 6

the jScience Library has a large vector called Float64Vector. While I have never used this Class it might fit your needs. No promises.

EDIT: Zach Scrivena pointed out in the comments that the Float64Vector is dimensioned to ints. I stand corrected.

Answer 7

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.