java - 欧拉项目 #10，java，适用于小数

Question

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

*目标，求出所有小于等于2,000,000(两百万)的质数之和

*问题，只要我的测试值范围大约小于或等于，我的代码就会输出正确的结果

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

测试输入:----199,999测试输出:---1,709,600,813正确结果:1,709,600,813

测试输入:----799,999测试输出:---24,465,663,438正确结果:24,465,663,438

测试输入:----1,249,999测试输出:---57,759,511,224正确结果:57,759,511,224

测试输入:----1,499,999测试输出:--- 82,075,943,263正确结果:82,074,443,256

测试输入:----1,999,999测试输出:--- 142,915,828,925正确结果:142,913,828,925

测试输入:----49,999,999测试输出:--- 72,619,598,630,294正确结果:72,619,548,630,277

*我的代码，发生了什么，为什么它适用于较小的输入？我什至使用 long，而不是 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的情况下，这让the next prime after 1,999,999, which is 2,000,003 .你会注意到 the correct value, 142,913,828,922,正好比您的结果 142,915,828,925 少 2,000,003。

更简单的结构

这是代码结构的一种方式，使用标签和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;
}