수천 개의 숫자를 신속하게 추가하는 효율적인 방법은 무엇입니까?

Question

나는 도전 과제를 풀려고 시도하고 있지만, 나는 장애물에 부딪쳤다. 나는 수만 개의 숫자를 추가하려는 초보 프로그래머이다. 내가 충분히 오래 기다리면 내 프로그램에서 쉽게 정확한 합계를 얻을 수 있지만 더 효율적인 방법을 찾고 있습니다.

수천 개의 숫자를 신속하게 추가하는 효율적인 방법은 무엇입니까?

사이드 노트 : 저는 모듈러 산술에 대해 읽었지 만 주위를 감싸고있을 수는 없습니다. 이 상황에 유용 할 지 확신 할 수 없습니다. 내가 여기에 2 000 000 이하의 모든 소수의 합계를 얻기 위해 시도하고

지금까지 내 코드입니다 :이 숙제처럼 보이는

public class Problem10 { 
    public static void main (String[] args) { 
     long sum = 0L; 

     for(long i = 1L; i < 2000000; i++) { 
      if(isPrimeNumber((int)i)) { 
       sum += i; 
      } 
     } 
     System.out.println(sum); 
    } 

    public static boolean isPrimeNumber(int i) { 
     int factors = 0; 
     int j = 1; 

     while (j <= i) { 
      if (i % j == 0) { 
       factors++; 
      } 
      j++; 
     } 
     return (factors == 2); 
    } 
} 

Answer 1

isPrimeNumber() 메서드를 사용하여 대체 할 수 있습니다.

public static boolean isPrimeNumber(int i) { 
    if (i==2) return true; 
    if (i==3) return true; 
    if (i%2==0) return false; 
    if (i%3==0) return false; 

    int j = 5; 
    int k = 2; 

    while (j * j <= i) { 
     if (i % j == 0) return false; 
     j += k ; 
     k = 6 - k; 

    } 
    return true; 
} 

Answer 2

, 그래서 나는 당신에게 솔루션을 제공하지 않을거야 코드에서. 당신이 할 수있는 일은 코드를 직접 작성하는 것입니다. 내가 추측했다 코드에서

---

, isPrimeNumber()이 대부분 차지 무슨 경우 시간을-, 나는 그것의 90-99%을 말할 것입니다. 더 빨리 만들 수있는 방법은 Sieve of Eratosthenes을 구현하는 것입니다.

시작하려면 모든 소수를 포함하는 배열을 만듭니다 . 단일 값으로 시작해야합니다 : 2. 더 많은 소수를 찾으려면 3에서 원하는 가장 높은 수까지 모든 정수를 반복합니다. 각 숫자에 대해 해당 숫자가 배열의 소수로 나눌 수 있는지 확인하십시오. 배열의 다음 소수가 i/2보다 큰 경우 i이 소수이며 배열에 추가 할 수 있음을 알 수 있습니다.

1에서 n까지 모든 소수를 찾았 으면 합계를 만드는 유일한 방법은 배열을 반복하는 것입니다. 이 부분은 최적화 할 수 없지만 어쨌든 오래 걸리지는 않습니다.

이렇게하는 데는 두 가지 방법이 있습니다. 하나는 ArrayList 또는 LinkedList를 사용하고 필요에 따라 숫자를 추가하는 것입니다. 다른 하나는 필요한 것보다 크거나 큰 배열을 만드는 것입니다. here 바와 같이, 같거나 n보다 작은 소수의 개수만큼, n이 598보다 작 으면, n이 598보다 큰 경우로, 방금 길이의 배열을 만들 수 있으며, 이하 (n/log(n)) * (1 + 1.2762/log(n)) 인 109

---

"수천 개의 숫자를 빠르게 추가하는 효율적인 방법은 무엇입니까?"라는 제목의 질문과 관련하여 내가 생각할 수있는 유일한 것은 다중 스레드입니다. 합계하려는 모든 숫자의 배열을 만든 다음 많은 스레드가 배열의 다른 부분을 합계하도록하십시오. 그 후에 각 스레드의 모든 결과를 합산하십시오. 이 방법은 방대한 양의 숫자를 합산 할 때만 눈에 띄게 빠릅니다. 수십만 또는 수백만