1

试图在项目 euler 上实现一个简单的 Erathostenes 筛来解决这个问题:

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

求两百万以下的所有素数之和。

关联

但是,我的代码不断返回此错误:

线程“主”java.lang.ArrayIndexOutOfBoundsException 中的异常:Prime.main 的 -2147479015(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);

    }

}
4

2 回答 2

4

问题来自以下几行:

        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。

于 2011-10-09T23:52:50.650 回答
2

不要刻薄,但这是因为您超出了数组的范围。您的限制i是数组的长度,然后j至少等于 的平方ij然后被用作要在第 28 行访问的数组的位置,这是超出范围的。

于 2011-10-09T23:51:20.800 回答