Erathostenes筛子ArrayIndexOutOfBounds [英] Sieve of Erathostenes ArrayIndexOutOfBounds

问题描述

试图实现简单的松软筛网来解决欧拉项目上的这个问题:

trying to implement a simple sieve of erathosthenes to solve this question on project euler :

低于10的素数之和是2 + 3 + 5 + 7 = 17.

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

找到200万以下的所有素数之和.

Find the sum of all the primes below two million.

链接

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

My code keeps returning this error however :

线程主"中的异常java.lang.ArrayIndexOutOfBoundsException: 在Prime.main(Prime.java:28)上-2147479015

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -2147479015 at Prime.main(Prime.java:28)

任何人都可以给我关于为什么的任何提示吗?这是代码:

Can anyone give me any hints as to why? Here is the code:

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

    }

}

推荐答案

问题来自以下几行:

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

正在发生的事情是，有时i * i太大，以至于拐弯处(溢出)并变为负数. Java没有检查"整数数学.要解决此问题，您需要将while条件更改为以下

What's happening is that sometimes i * i is so big that it rounds the corner (overflows) and becomes negative. Java does not have 'checked' integer math. To fix this, you'll want to change your while condition to the following

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

另外，您的数组大小为200,000，而不是2,000,000.

Also, your array is of size 200,000 and not 2,000,000.

这篇关于Erathostenes筛子ArrayIndexOutOfBounds的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！