质数计算器需要太多时间 (JAVA)

Question

当我运行此代码查找小于 20 的质数之和时，它工作正常，但当尝试查找小于 2500000 的总和时，它需要太多时间。已经至少 20 分钟了，而且还运行宁。好像不行。我该如何解决？

class PrimeSummation {
    public static void main(String[] args) {
        int sum = 0;
        for(int i = 1; i < 2500000; i++) {
            int count = 0;
            for(int j = 1; j < i + 1; j++) {
                if((i%j) == 0) {
                    count++;
                }
            }
            if(count == 2) {
                sum += i;
            }
        }
        System.out.println(sum);
    }
}

Answer 1

跟踪以前发现的素数似乎有帮助：

    BigInteger sum = BigInteger.ZERO;
    List<Integer> primes = new ArrayList<>();
    for(int i = 2; i < 2500000; i++) {
        boolean isPrime = true;
        for(int j = 0; j < primes.size() && primes.get(j)<= Math.sqrt(i); j++) {
            int p = primes.get(j);
            if((i%p) == 0) {
                isPrime=false;
                break;
            }
        }
        if(isPrime) {
            sum = sum.add(BigInteger.valueOf(i));
            primes.add(i);
        }
    }
    System.out.println(sum);

得出答案：

219697708195

Answer 2

如果您想要更好的性能来生成大量 prime number，您应该使用 Sieve formula。

您可以学习 Sieve_of_Eratosthenes 素数生成公式。

根据Sieve_of_Eratosthenes：

import java.util.*;

public class Sieve
{
    private BitSet sieve;

    private Sieve() {}

    private Sieve(int size) {
        sieve = new BitSet((size+1)/2);
    }

    private boolean is_composite(int k)
    {
        assert k >= 3 && (k % 2) == 1;
        return sieve.get((k-3)/2);
    }

    private void set_composite(int k)
    {
        assert k >= 3 && (k % 2) == 1;
        sieve.set((k-3)/2);
    }

    public static List<Integer> sieve_of_eratosthenes(int max)
    {
        Sieve sieve = new Sieve(max + 1); // +1 to include max itself
        for (int i = 3; i*i <= max; i += 2) {
            if (sieve.is_composite(i))
                continue;

            // We increment by 2*i to skip even multiples of i
            for (int multiple_i = i*i; multiple_i <= max; multiple_i += 2*i)
                sieve.set_composite(multiple_i);

        }
        List<Integer> primes = new ArrayList<Integer>();
        primes.add(2);
        for (int i = 3; i <= max; i += 2)
            if (!sieve.is_composite(i))
                primes.add(i);

        return primes;
    }
}

性能：

Answer 3

sum 不能是 int 因为答案是 219697708195 而 Integer.MAX_VALUE 只是 2147483647。您必须改用 long 或 BigInteger。

你的算法非常慢，因为对于 2500000 个数字中的每一个你都从头开始判断它是否是质数，而你测试一个数是否是质数的方法（尝试每个可能因素）效率不高。

以下代码在我的机器上大约在十分之一秒内生成答案。

int num = 2500000;
long sum = 0;
boolean[] arr = new boolean[num];
for (int p = 2; p < num; p++) {
    if (!arr[p]) {
        sum += p;
        for (int k = p * 2; k < num; k += p)
            arr[k] = true;
    }
}
System.out.println(sum);

质数计算器需要太多时间 (JAVA)

Prime numbers calculator takes too much time (JAVA)

java

primes