何千もの数字をすばやく追加する効率的な方法は何ですか？

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までのすべての素数を見つけたら、それらを合計する唯一の方法は配列を反復することです。その部分は最適化することはできませんが、とにかく長くかかることはありません。

これを行うには2通りの方法があります。 1つは、ArrayListまたはLinkedListを使用し、必要に応じて数値を追加することです。もう1つは、必要以上に大きなアレイを作成することです。 here述べたように、n以下の素数の数であればnが598未満である場合、nが598よりも大きいように、あなただけの長さの配列を作成することができ、以下(n/log(n)) * (1 + 1.2762/log(n))ある109

---

「何千もの数字をすばやく追加する効率的な方法は何ですか？」というタイトルの質問に関しては、私が考えることができるのはマルチスレッドです。合計したいすべての数値の配列を作成し、多くのスレッドが配列の異なる部分を合計するようにします。その後、各スレッドからすべての結果を合計します。このメソッドはおそらく、膨大な数の数値を合計する場合に顕著に高速になります。何百、何千または何百万。