当我运行此代码来查找低于 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);
}
}
最佳答案
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 - 素数计算器需要太多时间(JAVA),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32417266/