StackOverflowError eratosthenes sieve implementation

Question

I have tried to implement Eratosthenes sieve in Java, but I have a StackOverflowError like this:

Exception in thread "main" java.lang.StackOverflowError
at com.company.era2.sieve(era2.java:24)
at com.company.era2.sieve(era2.java:24)
at com.company.era2.sieve(era2.java:24)

Seems like its infinite recursion, but algo works fine and fast with n <= 90000
What could I do wrong? Code:

public class era2 {
public static void print(Object x) {
    System.out.println(x);
}
public static List<Integer> sieve(List<Integer> array, int index, int last_crossed){
    if (index >= array.size() - 1){
        print("Last crossed number : "  + last_crossed);
        return array;
    } else {
        for (int i = index + 1; i <= array.size() - 1; i++){
            int num = array.get(i);
            if (num % array.get(index) == 0) {
                array.remove(i);
                i--;
                last_crossed = num;
            }
        }
        return (sieve(array,index + 1, last_crossed));
    }
}
public static void main(String[] args) {
    int n = 1000000;
    List<Integer> arr = new ArrayList<>();
    for (int i = 2; i <= n; i++){
        arr.add(i);
    }
    arr = sieve(arr, 0, 0);
    for (int x : arr){
        print(x);
    }
}
}

You don't need infinite recursion to get a StackOverflowError, a finite but large amount of recursion will do that just fine ;). If you have enough memory, there is probably a command-line option to increase the maximum size of the stack, but there will always be some finite limit — OpenSauce, Sep 16 '18 at 15:36
See https://stackoverflow.com/questions/20030120/what-is-the-default-stack-size-can-it-grow-how-does-it-work-with-garbage-colle for info. — Markus, Sep 16 '18 at 16:16
@OpenSauce apparently, I didn't have enough stack size memory. Now it works. — ramazan793, Sep 16 '18 at 18:29

score 0 · Accepted Answer · answered Sep 16 '18 at 18:03

If you don't necessarily need to use recursion here is a solution inspired by this wikipedia article

public static List<Integer> sieve(int limit) {
    boolean[] array = new boolean[limit - 2];
    Arrays.fill(array, true);
    int end = (int)Math.sqrt(limit);

    for (int i = 2; i <= end; i++) {
        if (array[i - 2]) {
            int j = i * i;
            int k = 0;
            while (j < limit) {
                array[j - 2] = false;
                j = i * i + i * ++k;
            }
        }
    }

    List<Integer> result = new ArrayList<>();
    for (int l = 2; l < limit; l++) {
        if (array[l - 2]) {
            result.add(l);
        }
    }

    return result;
}

It is not necessarily, but i thought recursion would be more scientific way. But also recursion works by increasing stack memory to 512M. — ramazan793, Sep 16 '18 at 18:18

StackOverflowError eratosthenes sieve implementation

1 Answers1