Sieve Eratosthenes greater than int

Question

I want to find all the prime numbers under 10 billion. Which is 5 times as big as int can hold (which is the limitation of arrays regardless of type). Attempting to allocate over 1.2billion at a time results in out of heap space error. I tried using List instead of a boolean array, but the set element method for arrayLists only indexes up to int. What bugs me, is that pretty quickly into the sieve there are less than an integer number of elements not crossed off. One method that should work, would be to create a partition of 10 arrays and smash them together... but that would be ugly. Let me know if you have any suggestions of an elegant way to solve this. (Other than using Python lol). I already have an n^2/2 brute force implementation, but that takes a long time to run so really I want to solve this as big O fast as possible. My Sieve implementation that works up to 1.2Billion is as follows:

public class SieveEratosthenes {
private boolean[] nums;
public static void main(String[] args) {
    int n = 1000000;
    SieveEratosthenes s = new SieveEratosthenes(n);
    for(int i=0;i<s.nums.length;i++){
        if(s.nums[i]){
            System.out.println(i);
        }
    }
}

public SieveEratosthenes(int max){
    sieve(max);
}

private boolean[] sieve(int max){
    nums = new boolean[max+1];
    initFlags();
    for(int i=2;i*i<max;i++){
        for(int j=i*i;j<=max;j+=i){//cross off non-primes
            nums[j]=false;
        }
    }
    return nums;
}
private void initFlags(){
    if(nums != null&&nums.length>1){
        nums[0]=false;
        nums[1]=false;
        nums[2]=true;
    }
    for(int i=3;i<nums.length;i++){
        nums[i]=true;
    }
}

public List<Long> sieveToList(){
    List<Long> sieveList = new ArrayList();
    for(int i=0;i<nums.length;i++){
        if(nums[i]){
            sieveList.add((long)i);
        }
    }
    return sieveList;
}

Answer 1

Here is one approach that you can use:

• Use sieve for 10^7 ints or whatever size is suitable for you.
• Then, for every implementation of sieve, at the end, save all computed primes in any data-structure you are comfortable with (ArrayList would do).
• Now, do this for 1000 times, using loop (of course) and every time, your sieve would compute primes in next 10^7 range. So, on 1st iteration, all primes from 0-10^7 would be computed. Then, from 10^7+1 to 2*10^7 and so on.

PS: If you want the code, I'll do it for you but I recommend you to try it once. I may be wrong on this but I think this approach is what they call segmented sieve.

Answer 2

You should probably move away from using arrays for this. As you say they are not well suited to very large sets. A reasonable approximation of the algorithm is to 'cross out' as you examine each prime by testing it it's a multiple of any previous primes. I haven't analysed the performance of this.

class Sieve {
    private long current = 2;
    private final List<Long> primes = new ArrayList<>();

    public long nextPrime() {
        while (primes.stream().anyMatch(p -> current % p == 0))
            current++;
        primes.add(current);
        return current;
    }
}

Answer 3

If memory isn't an issue, continue using an array because it is much faster. If memory becomes an issue, I would suggest looking into BitSets.

While Java data structures are limited (as far as I know) to the maximum int size at around 2 billion, you could create your own data structure. A very simple solution would be to create a class that splits up your requested size into several arrays or bitsets given the max int length, and then automatically accesses them given by a long index input that you enter. I hope that makes sense. Let me know if you have any questions!