When I run this code to find sum of prime numbers below 20 it works fine, but when try to find sum below 2500000 it takes too much time. It's been at least 20 minutes and it's still running. It seems like it's not working. How do I fix it?
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 cannot be an int because the answer is 219697708195 whereas Integer.MAX_VALUE is only 2147483647. You must use a long or a BigInteger instead.
Your algorithm is very slow, because for every one of the 2500000 numbers you are starting from scratch to decide whether it is prime or not, and your approach for testing whether a number is prime (try every possible factor) is not very efficient.
다음 코드는 내 컴퓨터에서 약 10 분의 1 초 안에 답변을 생성합니다.
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);
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다