埃拉托斯特尼筛法 ArrayIndexOutOfBounds

Question

尝试实现一个简单的erathosthenes筛来解决euler项目上的这个问题：

10 以下的素数之和为 2 + 3 + 5 + 7 = 17。

求 200 万以下所有素数的和。

链接

但是，我的代码不断返回此错误：

线程“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 行要访问的数组的位置，这是越界的。