java - 求 200 万以下所有素数的和

Question

这个问题已经有答案了:

已关闭 10 年前。

Possible Duplicate:
How much time should it take to find the sum of all prime numbers less than 2 million?

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

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

Find the sum of all the primes below two million.

Link

尽管如此，我的代码不断返回错误的答案 - 我不断收到 142889228620，该项目 euler 不接受。

谁能给我任何关于为什么的提示？这是代码:

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

对于较大的 i 值，这会溢出:

int j = i * i;

解决这个问题的一种方法是使用long，因为这样大小的数字不会溢出。然后，您还可以删除测试 j > 0，因为 j 仅在发生溢出时才变为负值。我猜您添加了该测试，因为没有它就崩溃了，但没有注意到溢出可能会严重到您也可能会得到错误的正值，这会导致错误的数字在您的代码中被划掉。筛子，给你不正确的结果。

素数 i = 92683 就是一个说明这种情况如何引起麻烦的例子。使用int算术，i * i溢出到203897，它也是一个素数，但会被错误地划掉。

这是使用long算术的简单修复:

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

我已经验证这给出了正确的答案。

我们可以进一步改进这一点，注意一旦i*i >= array.length，我们就可以跳出外循环，因为内循环将永远不会运行。我们可以通过将外循环的条件更改为:

for(int i = 2; i * i < array.length; i++)

在这里，我们可以再次使用int，因为循环将在数字变得太大而溢出之前结束。