Сито из эратостенов ArrayIndexOutOfBounds

Question

пытается внедрить простое сито из эратфосфена для решения этого вопроса на проекте Эйлера:

Сумма простых чисел ниже 10 составляет 2 + 3 + 5 + 7 = 17.

Найдите сумму всех простых чисел ниже двух миллионов.

Ссылка

Мой код продолжает возвращать эту ошибку, однако:

Исключение в потоке "main" java.lang.ArrayIndexOutOfBoundsException: -2147479015 в Prime.main (Prime.java:28)

Может кто-нибудь дать мне какие-нибудь подсказки, почему?Вот код:

import java.math.BigInteger;

public class Prime {
    /*
     * Input: an integer n > 1
     * 
     * Let A be an array of bool values, indexed by integers 2 to n, initially
     * all set to true.
     * 
     * for i = 2, 3, 4, ..., while i^2 ≤ n: if A[i] is true: for j = i^2, i^2 +
     * i, i^2 + 2i, ..., while j ≤ n: A[j] = false
     * 
     * Now all i such that A[i] is true are prime.
     */

        import java.math.BigInteger;

public class Prime {
    /*
     * Input: an integer n > 1
     * 
     * Let A be an array of bool values, indexed by integers 2 to n, initially
     * all set to true.
     * 
     * for i = 2, 3, 4, ..., while i^2 ≤ n: if A[i] is true: for j = i^2, i^2 +
     * i, i^2 + 2i, ..., while j ≤ n: A[j] = false
     * 
     * Now all i such that A[i] is true are prime.
     */

    public static void main(String[] args) {
        boolean[] array = new boolean[2000000];
        BigInteger counter = new BigInteger("0");
        for (int value = 0; value < array.length; value++) {
            array[value] = true;
        }
        for (int i = 2; i < array.length; i++) {
            if (array[i]) {
                int j = i * i;
                while (j > 0 && j < array.length) {
                    array[j] = false;
                    j += i;
                }
            }
        }
        for (int i = 2; i < array.length; i++) {
            if (array[i]) {
                counter = counter.add(BigInteger.valueOf(i));
            }
        }
        for (int value = 2; value < array.length; value++) {
            if(array[value]){
                System.out.println(value + ", ");
            }
        }
        System.out.println("\n" + counter);

    }

}

Answer 1

Проблема исходит от этих строк:

        int j = i * i;
        while (j <= array.length) {
            array[j] = false;
            j += i;
        }

То, что происходит, иногда i * i настолько велико, что закругляет угол (переполняется) и становится отрицательным. В Java нет проверенной целочисленной математики. Чтобы это исправить, вам нужно изменить условие while на следующее

while(j > 0 && j < array.length)

Кроме того, ваш массив имеет размер 200 000, а не 2 000 000.

Answer 2

Не для того, чтобы быть хитрым, но это потому, что вы выходите за пределы массива. Ваш предел для i равен длине массива, а затем j равен как минимум квадрату i. j затем используется в качестве местоположения массива для доступа к строке 28, которая находится за пределами.