StackOverflowError eratosthenes筛选实施

Question

我试图在Java中实现Eratosthenes筛，但是我有一个像这样的StackOverflowError：

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)

看起来像它的无限递归，但algo使用n <= 90000工作得很好 我该怎么办？码：

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);
    }
}
}

Answer 1

如果你不一定需要使用递归，这是一个灵感来自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;
}