java - 素数计算器需要太多时间(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

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);