项目euler #10，java，对小数字正确

Question

*免责声明，当我说“我已经证实这是正确的结果”时，请解释这一点，因为我已经根据WolframAlpha的答案检查了我的解决方案，我认为这是相当准确的。

*目标，求出小于或等于2,000,000 (200万)的所有素数之和

*当我的测试值范围大约小于或等于

一旦测试输入超过大约1,300,000，我就不会输出正确的结果；我的输出将关闭.

测试输入：

测试输入：

测试输入：

测试输入：

测试输入：

测试输入：

*我的代码，发生了什么，为什么它对较小的输入有效？我甚至用了很长的时间而不是int..。

long n = 3;
long i = 2;
long prime = 0;
long sum = 0;
while (n <= 1999999) {
  while (i <= Math.sqrt(n)) {    // since a number can only be divisible by all
                            // numbers
                            // less than or equal to its square roots, we only
                            // check from i up through n's square root!
    if (n % i != 0) {       // saves computation time
      i += 2;               // if there's a remainder, increment i and check again
    } else {
      i = 3;                // i doesn't need to go back to 2, because n+=2 means we'll
                            // only ever be checking odd numbers
      n += 2;               // makes it so we only check odd numbers
    }
  }                         // if there's not a remainder before i = n (meaning all numbers from 0
                            // to n were relatively prime) then move on
  prime = n;                // set the current prime to what that number n was
  sum = sum + prime;
  i = 3;                    // re-initialize i to 3
  n += 2;                   // increment n by 2 so that we can check the next odd number

}
System.out.println(sum+2); // adding 2 because we skip it at beginning

(请帮助:)

Answer 1

问题是，您没有正确地检查要添加到和中的最新质数是否小于极限。您有两个嵌套循环，但只检查外部循环的限制：

while (n <= 1999999) {

但是你不能在内部循环中签入：

 while (i <= Math.sqrt(n)) {

然而，在这个循环中，您反复地前进到下一个候选素数(n += 2;)。这允许候选素数超过限制，因为在外部循环的每次迭代中，只对第一个候选素数进行检查，而不是对内环访问的任何后续候选素数进行检查。

举个例子，在限制值为1,999,999的情况下，可以使用在1,999,999之后的下一个质数，即2,000,003。您将注意到，正确值，142,913,828,922，正好比您的结果142,915,828,925少2,000,003。

更简单的结构

这里有一种方法可以构造代码，使用带有该标签的label和continue来简化结构：

public static final long primeSum(final long maximum) {
    if (maximum < 2L) return 0L;
    long sum = 2L;

    // Put a label here so that we can skip to the next outer loop iteration.
    outerloop:
    for (long possPrime = 3L; possPrime <= maximum; possPrime += 2L) {
        for (long possDivisor = 3L; possDivisor*possDivisor <= possPrime; possDivisor += 2L) {
            // If we find a divisor, continue with the next outer loop iteration.
            if (possPrime % possDivisor == 0L) continue outerloop;
        }
        // This possible prime passed all tests, so it's an actual prime.
        sum += possPrime;
    }

    return sum;
}