-2

我试图找到数百万以下的素数之和。当我试图找到低于十万的素数总和时，我的代码有效，但是当我去大数字时它不起作用。所以我需要一些帮助来完成这项工作......

import java.util.Scanner;
public class sumPrime {

  public static void main (String args []){

    long n = 2000000; int i; int j;int sum =0;
    for (i=2; i <n; i++){
        for (j=2; j<i; j++){
            if (i%j==0){
                break;
            }
        }
        if (i==j){
            sum +=i;
        }
    }
    System.out.print(sum);
  }
}
4

4 回答 4

4

  1. 您的代码可以通过提前停止内部循环来改进。如果一个数N不是素数，那么它必须至少有一个因子（除了 1）小于或等于sqrt(N)。在这种情况下，这个简单的更改应该会使程序快大约 1000 倍。

  2. 对于简单且（更）有效的算法，请阅读埃拉托色尼筛。

  3. 错误 - 您sum需要成为long. 一个int可能会溢出。

请注意，埃拉托色尼筛法的经典公式需要大量布尔值（或位图），其大小取决于您感兴趣的最大素数候选者。在这种情况下，这意味着 2Mbyte 数组（如果您使用位图则更小） ...这太小了，不用担心。此外，您可以通过分阶段筛选来减少内存使用量，尽管这会使代码更加复杂。

于 2013-09-01T00:00:11.807 回答
2

与其尝试除以 i 下面的所有数字，不如将找到的素数保留在列表中并尝试除以这些素数（因为任何非素数都可以被小于该数的素数整除）。

public static long sumPrime2() {
    List<Long> primes = new ArrayList<>();
    primes.add(2L);
    primes.add(3L);
    long primeSum = 5;

    for (long primeCandidate = 5; primeCandidate < 2000000; primeCandidate = primeCandidate + 2) {
        boolean isCandidatePrime = true;
        double sqrt = Math.sqrt(primeCandidate);
        for (int i = 0; i < primes.size(); i++) {
            Long prime = primes.get(i);
            if (primeCandidate % prime == 0) {
                isCandidatePrime = false;
                break;
            }
            if (prime > sqrt) {
                break;
            }
        }
        if (isCandidatePrime) {
            primes.add(primeCandidate);
            primeSum += primeCandidate;
        }
        System.out.println(primeCandidate);
    }
    System.out.println(primes.size());
    return primeSum;
}

这在 8 秒内给出了答案

于 2013-09-01T05:13:45.953 回答
1

我怀疑 i、j、sum 中的整数溢出 - 尝试将它们全部设为 long。在示例代码中，您不应该出现溢出，因为 Java 整数是 32 位的，但在某些阶段您肯定会。

如前所述 - 我只需要迭代到 n 的平方根。所以我会替换这一行：

for (i=2; i <n; i++){

和：

long limit=sqrt(n);
for (i=2; i <limit; i++){

请注意，在程序循环之外计算平方根也会加快速度。

此外，筛算法会更快，但需要 Java 创建一个包含 n 个元素的数组，并且在某些阶段会因内存不足而失败。

于 2013-09-01T00:09:38.273 回答
0

该程序的最佳算法使用 Eratosthenes 筛法：

function sumPrimes(n)
    sum, sieve := 0, makeArray(2..n, True)
    for p from 2 to n
        if sieve[p]
            sum := sum + p
            for i from p*p to n step p
                sieve[i] := False
    return sum

然后sumPrimes(2000000)在大约一秒内返回小于 200 万的素数之和。我将把它留给您翻译成 Java，并为总和使用适当的数据类型。如果你对使用素数编程感兴趣，我在我的博客上谦虚地推荐这篇文章。

于 2013-09-01T12:24:40.817 回答