2

重複の可能性：
JavaでisPrimeを記述する最もエレガントな方法

これをより速くまたはより良くするにはどうすればよいですか？プロジェクトオイラーの問題を解決して最適化するために作成しましたが、これは最善の方法ではないと確信しています

public static boolean prime(int number){
    int limit = (int) (1 + Math.sqrt(number) );
    if (number < 1) return false;
    if (number == 2) return true;
    if (number % 2 == 0) return false;

    for(int i= 3; i < limit; i+=2)
        if(number % i == 0)
            return false;
    return true;
}
}
4

4 に答える 4

4

数値の処理を除いて1、関数はかなり見栄えがします。行うことができる1つの改善は、すべての素数3がの形式よりも大きいという事実を利用すること6k ± 1です。

さらに先に進むこともできますが、パフォーマンスの向上とコードの複雑さの増加のバランスをとる必要があります。

于 2012-12-16T20:45:12.303 に答える
3

あなたがどれだけ空想を得たいかによります。

簡単な改善の1つは、ホイール因数分解を使用することです。すべての奇数を試すのではなく（たとえば、 2で割り切れない数）、いくつかの小さな素数で割り切れない数だけを試します。たとえば、2または3で除算可能かどうかをチェックする実装を次に示します。

for (int i = 6; i < limit; i += 6) {
    if (number % (i + 1) == 0) return false;
    if (number % (i + 5) == 0) return false;
}

これは、コードの1/2ではなく、6つの数値ごとに2つのテストを実行するだけで済みます。素数を追加することでさらに改善できますが（ウィキペディアの記事のホイールは30のうち8をテストします）、コードサイズが急速に大きくなります。

真面目な数学で手を汚してもかまわないのなら、ミラーラビン素検定のような数論的な方法があります。適切な証人のセットを使用すると、これらの方法は、妥当な範囲内のすべての数値に対して確実に正しいことに注意してください（「テストの決定論的バリアント」を参照）。

于 2012-12-16T20:48:11.030 に答える
1 
BigInteger.valueOf(x).isProbablePrime(50)

1/1000000000000000のエラーの可能性を許容できると仮定すると、これはおそらく非常に高速です。

于 2012-12-16T20:47:45.017 に答える
0

エラトステネスのふるいをご覧 くださいhttp://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

于 2012-12-16T20:45:56.073 に答える