StackOverflowError eratosthenes ситовая реализация - PullRequest
0 голосов
/ 16 сентября 2018

Я пытался реализовать сито Эратосфена в Java, но у меня есть 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)

Похоже на его бесконечную рекурсию, но алгоритм работает отлично и быстро с 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);
    }
}
}

1 Ответ

0 голосов
/ 16 сентября 2018

Если вам не обязательно использовать рекурсию, вот решение, вдохновленное этой статьей в Википедии

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