3

そのため、私は自分のことをかなり初心者のプログラマーと呼んでいます。学校教育では主にハードウェアに集中しており、コンピューター サイエンスのコースはあまり多くありませんでした。

そこで、Project Euler の問題 7 を解決しました。

最初の 6 つの素数 (2、3、5、7、11、13) をリストすると、6 番目の素数が 13 であることがわかります。

10001番目の素数は何ですか?

Javaで問題なくこれを解決できましたが、ソリューションを実行すると、実行に8秒かかりました。数学的な観点ではなく、プログラミングの観点からこれをどのように最適化できるか疑問に思っていました。

配列がループしているか、主に while ステートメントが処理時間を消費していますか? そして、これをどのように最適化できますか? 繰り返しますが、派手な数式を探しているわけではありません..ソリューションスレッドにはそれらがたくさんあります.

スポイラー私の解決策を以下に示します。

public class PrimeNumberList {

private ArrayList<BigInteger> primesList = new ArrayList<BigInteger>();

public void fillList(int numberOfPrimes) {
    primesList.add(new BigInteger("2"));
    primesList.add(new BigInteger("3"));
    while (primesList.size() < numberOfPrimes){
        getNextPrime();
    }
}

private void getNextPrime() {
    BigInteger lastPrime = primesList.get(primesList.size()-1);
    BigInteger currentTestNumber = lastPrime;
    BigInteger modulusResult;
    boolean prime = false;
    while(!prime){
        prime = true;
        currentTestNumber = currentTestNumber.add(new BigInteger("2"));
        for (BigInteger bi : primesList){
            modulusResult = currentTestNumber.mod(bi);
            if (modulusResult.equals(BigInteger.ZERO)){
                prime = false;
                break;
            }
        }
        if(prime){
            primesList.add(currentTestNumber);
        }
    }
}

public BigInteger get(int primeTerm) {
    return primesList.get(primeTerm - 1);
}

}

4

9 に答える 9

13

10001 番目の素数はそれほど大きくないので、long代わりに を使用して開始できますBigInteger。BigIntegerインスタンスは本格的な Java オブジェクトであり、インスタンスの作成と操作には多くのオーバーヘッドがあります。

于 2010-04-19T15:44:16.627 に答える
6

自分でベンチマークすることもできますが、for (BigInteger bi : primesList)ループはほとんどの時間を費やしている場所だと思います。素数のリスト全体をループしています。素数性をテストしている数の平方根よりも大きい素数候補除数に到達するとすぐに、そのループから抜け出すことができます。

もう 1 つの (比較すると非常にわずかな) 改善点は、while ループのたびに同じ値new BigInteger("2")で新しい値を作成する代わりに、キャッシュして再利用することです。BigInteger<-- 良い習慣ですが、この場合は丸め誤差ほど重要ではありません。

于 2010-04-19T15:46:22.473 に答える
4

また、ビットセットで表される素数でエラトステネスのふるいを試してみてください。候補を個別にテストするよりもはるかに高速です。

于 2010-04-19T19:27:24.953 に答える
1

intsを使用します。primesListに固定サイズの配列を使用して、メモリの割り当てにお金を払う必要がないようにします（または、動的リストが問題にならないように開始サイズを十分に大きくします）。

代わりにintをカウントする法線を使用し、Countはループの外側にあります。

于 2010-04-19T15:53:45.047 に答える
1

int/long を使用したほうがよいでしょう。ループを実行して、数値が素数かどうかを確認してください。プログラムを最適化して高速化するには、制限を Math.sqrt(num) に設定して for ループの反復を減らすことができます。

参考：http ://www.mycoding.net/2012/01/program-to-find-10001st-prime-number-project-euler-problem-7/

于 2012-01-17T06:16:09.923 に答える
1

でループしているwhile(!prime)のでgetNextPrime()、素数を返すことが保証されているため、毎回fillList呼び出すことなくループを変更できます。size()おそらくそれほど大きくはありませんが、1 ずつインクリメントされていることがわかっている場合に毎回サイズを計算するのはちょっと意味がありません。

LinkedListまた、 の代わりに を試すこともできますArrayList。この特定のユースケースでは、実際にはより高速になる可能性があります。

于 2010-04-19T16:40:43.347 に答える
0

あなたのコードは、2 で割り切れるすべての候補をテストしていることに気付きました。しかし、あなたの最有力候補は決して平等ではありません。したがって、この最初のテストをスキップできます。ちょっとしたことですが、9999 個のモッドを節約できます。

于 2010-04-19T16:19:51.900 に答える
0

Here is a .NET solution... My tests indicated that I received the 10001st prime in 132ms, and 100,000 prime in 4417ms.

public static IEnumerable<long> GetPrimes(int numberPrimes)
{
  List<long> primes = new List<long> { 1, 2, 3 };
  long startTest = 3;

  while (primes.Count() < numberPrimes)
  {
    startTest += 2;
    bool prime = true;
    for (int pos = 2; pos < primes.Count() && primes[pos] < Math.Sqrt(startTest); pos++)
    {
      if (startTest % primes[pos] == 0)
      {
        prime = false;
      }
    }
    if (prime)
      primes.Add(startTest);
  }
  return primes;
}
于 2010-04-19T19:51:18.990 に答える
0

エラトステネスのふるいを Javaに翻訳しただけです。これは、素数をアルゴリズム的に解く最も効率的な方法の 1 つと考えられています。

public static void main(String[] args){

    ArrayList<Integer> List = new ArrayList<Integer>();
    ArrayList<Integer> Primes = new ArrayList<Integer>();
    Primes.add(2);
    Integer p=2;
    Integer n=105000; 
    Integer i=1;

    while(p < n) {

        i=1;

        while((p*i)<=n) {
            List.add(p*i);
            i++;
        }

        while (p < n) {
            p++;
            if(List.contains(p)){                     }
            else                {Primes.add(p); break;}
        }

    }

    System.out.println("PRIME 10,001 is.... " + Primes.get(10000));
    // 104743

}
于 2014-03-10T20:49:57.910 に答える