稀土ArrayIndexOutOfBounds筛分

Question

为了解决euler项目中的这个问题，尝试实现一个简单的erathosthenes筛子：

低于10的素数之和为2+3+5+7= 17。 找出二百万以下所有素数的总和。

链接

但是，我的代码一直返回此错误：

线程"main“java.lang.ArrayIndexOutOfBoundsException：-2147479015 at 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行访问的数组的位置，这是超出界限的。