java - 寻找更大素数时出错

Question

我制作了一个简单的erastothenes 筛程序来计算欧拉项目的n 以内的素数之和。它适用于 100、1,000、10,000 等，但当我执行 1 或 200 万时，它会给出以下结果:

java.lang.ArrayIndexOutOfBoundsException:-2146737495

对于较小的数字，不会发生这种情况，我使用 boolean 数组。

boolean[] primes = new boolean[2000001];
    ArrayList<Integer> list = new ArrayList<Integer>();
    for (int i = 2; i < primes.length; i++){
        primes[i] = true;
    }
    boolean stop = false;
    int target = 2;
    int cycles = 1;
    while (!stop) {
        list.add(target);
        for (int i = target;; i ++) //
        {
            if (target*i >= primes.length ) {//
                break;
            }
            primes[target*i] = false;//

        }
        for (int i = target + 1; ; i ++) {

            if(i >= primes.length) {
                stop = true;
                break;
            }
             else if (primes[i]) {
                target = i;
                break;
            }
        }
        cycles ++;
    }
    int sum = 0;
        for (int i = 0; i < list.size(); i++) {
        sum += list.get(i);;
    }

我的目标根本不是真正找到答案，但很多时候我因为这些类型的错误而放弃了我的代码。我想找到它们的来源。

Answer 1

您的检查有错误，没有考虑整数溢出。

for (int i = target;; i ++) //
{
    if (target*i >= primes.length ) {// This is the check
        break;
    }
    primes[target*i] = false;// Here is where it overflows

}

一旦你命中一个i，使得target * i大于整数所能容纳的大小，整数就会溢出。这意味着现在它将变成负值。当然，对于负数，target*i >= primes.length 将为 false。

当然，负数不能作为数组中的索引。它应该在休息时停止，但它没有停止，因为条件不满足。

你应该做的是计算允许的最大i，并将其作为循环条件:

int maxI = primes.length / target;
for (int i = target; i < maxI; i ++) //
{
    primes[target*i] = false;// Here is where it overflows
}

maxI 是您可以乘以 target 但仍达不到 primes.length 的最大数字。现在您不再需要检查(因为将 target 乘以 i 永远不会产生大于 primes.length 的数字。而且它将也永远不会溢出，因为乘法总是产生一个小于数组大小的数字，因此小于 Integer.MAX_VALUE。

另一种更便宜(更少的乘法)的方法是:

if ( primes.length / target >= target ) {
    for (int i = target * target; i < primes.length; i += target ) //
    {
        primes[i] = false;
    }
}

如果您有一个巨大的目标，则有必要在if中进行检查以避免溢出。