项目Euler＃10 Java解决方案无法正常工作

我试图找到素数<2,000,000的总和。 这是我在Java中的解决方案，但我似乎无法得到正确的答案。 请对可能出现的错误提供一些意见，并对该代码的一般建议表示赞赏。

打印’sum’给出：1308111344，这是不正确的。

编辑：感谢您的帮助。 将int更改为long和<to <=并且它完美无缺，除了是找到素数的低效方法:)

/* The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million. */ class Helper{ public void run(){ Integer sum = 0; for(int i = 2; i < 2000000; i++){ if(isPrime(i)) sum += i; } System.out.println(sum); } private boolean isPrime(int nr){ if(nr == 2) return true; else if(nr == 1) return false; if(nr % 2 == 0) return false; for(int i = 3; i < Math.sqrt(nr); i += 2){ if(nr % i == 0) return false; } return true; } } class Problem{ public static void main(String[] args){ Helper p = new Helper(); p.run(); } } 

Answer 1

结果将太大而无法放入整数，因此您将获得溢出 。 尝试使用BigInteger或long 。 在这种情况下，长就足够了。

Answer 2

你将那些只能被平方根整除的数字（如25）视为素数。 而不是i < Math.sqrt(nr)尝试i <= Math.sqrt(nr) 。

顺便提一下，这是找到素数的一种非常低效的方法。

Answer 3

你的isPrime不适用于正方形。 isPrime（9）返回true。

Answer 4

如前所述，错误有两个：

• 你使用了一个不足以容纳这笔金额的int ..你应该用了long
• 你使用<而不是<= ，这是一个错误的守卫

除了你正在做的事情是非常低效的，没有深入这类算法（如Miller-Rabin测试），我建议你去看看Eratosthenes的Sieve ..一个很老的方法教会如何以简单的方式处理复杂的问题，通过记忆的权衡来提高优雅和效率。

它真的很敏锐：它会跟踪每个素数的boolean值，如果该数字是素数，则会断言。 然后从第一个素数开始，它排除了通过乘以正在分析另一个数的素数而获得的所有连续数。 更多的是，它需要检查更少的数字（因为它已经排除了它们）

代码很简单（只是动态编写，没有检查）：

  boolean[] numbers = new boolean[2000000]; long sum = 0; for (int i = 0; i < numbers.length; ++i) numbers[i] = true; for (int i = 2; i < numbers.length; ++i) if (!numbers[i]) continue; else { int j = i + i; while (j < 2000000) { numbers[j] = false; j += i; } } for (int i = 2; i < 2000000; ++i) sum += numbers[i] ? i : 0; System.out.println(sum); 

当然这种方法仍然不适合高数字（因为它必须找到所有以前的素数而且因为记忆）但是这是初学者思考问题的一个很好的例子。

Answer 5

通过有效地使用Sieve of Eratosthenes ，我解决了问题，这是我的代码

 public class SumOfPrime { static void findSum() { long i=3; long sum=0; int count=0; boolean[] array = new boolean[2000000]; for(long j=0;j 

而输出是

 Sum=142913828922 Count=148933 Time for execution=2360ms 

如果您有疑问，请告诉我们

Answer 6

这是我的解决方案

  public class ProjectEuler { public static boolean isPrime(int i) { if (i < 2) { return false; } else if (i % 2 == 0 && i != 2) { return false; } else { for (int j = 3; j <= Math.sqrt(i); j = j + 2) { if (i % j == 0) { return false; } } return true; } } public static long sumOfAllPrime(int number){ long sum = 2; for (int i = 3; i <= number; i += 2) { if (isPrime(i)) { sum += i; } } return sum; } /** * @param args */ public static void main(String[] args) { System.out.println(sumOfAllPrime(2000000)); } }