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