2

数が素数であるかどうかを調べるために、最速のアルゴリズムを作成しようとしています。私はこれを3から100,000までの数字ごとに行っています。

   for(int i = 3; i < 100000; i += 1)
        if(isPrime(i))
            System.out.println(i);

そしてそれは0.52秒かかります。私の友人は偶数を繰り返さないことを提案しました：

for(int i = 3; i < 100000; i += 2)
        if(isPrime(i))
            System.out.println(i);

そしてそれは0.53秒かかります（おそらくランダムな違い）。

なぜ彼の提案は実行時間を短縮しないのですか？より少ない数で反復する場合、プログラムはより速く実行されると思います。

isPrime（）のコード：

public static boolean isPrime(int n)
{
    if((n % 2 == 0 && n != 2) || (n % 3 == 0  && n != 3)|| (n % 5 == 0 && n != 5))
        return false;
    for(int i = 5; i < n / 5; i += 2)
    {
        if(n % i == 0)
            return false;
    }
    return true;
}
4

6 に答える 6

9

ほとんどの場合、素数をコンソールに印刷するために大部分の時間が必要です。したがって、素数の数も減らさなければ、テストされる数を減らしてもプログラムの速度に特に影響はありません。

次のように、素数を文字列にまとめて1回印刷してみてください。

StringBuilder b = new StringBuilder();
for(int i = 3; i < 100000; i += 1)
    if(isPrime(i))
      b.append(i).append("\n");

System.out.println(b.toString());
于 2013-02-28T12:50:11.773 に答える
4

アルゴリズムの問​​題は別として、ボトルネックはおそらくSystem.outストリームへの書き込みです。これは時間のかかる作業です。その部分をベンチマークループから除外する必要があると思います。これをすばやくテストするには、コメントアウトします（対応するifステートメントを使用）。

int iterations=100000;
long time = System.nanoTime();
for(int i = 3; i < 100000; i += 2) { //notice: always use curly brackets!!!
    isPrime(i);
}
long endTime = System.nanoTime();
System.out.println("Time to go through " + iterations + " iterations: " + (endTime>time?endTime-time:endTime+time));
//notice: nanoTime might turn around, resulting in smaller (negative) endTime value

また、トーマスの答えはこの問題に関してはるかに詳細System.out.printであり、多くの文字列を連結する適切なアプローチも提供します。

アルゴリズムの問​​題：

エラトステネスのふるいアプローチを使用している場合は、次の素数を検索するときに、すべての小さい素数をすでに見つけています。したがって、それらを保存する必要があります。5を超えるすべての奇数をチェックする代わりに、すでに持っているものだけをチェックする必要があります。

また、同時に、それらすべてをチェックする必要はありません。あなたの数の平方根以下であるものだけをチェックする必要があります。

//suppose we have a List<Integer> primeList (populated by previous execution loops)
// and Integer numberTested as the number under testing

for(int i=0; i<primeList.size();i++) {
    if(numberTested%primeList.get(i)==0) {
        //divider found, not prime
        break;
    }        

    if(primeList.get(i)>Math.sqrt(numberTested)) {
        //still not found a divider -- we found a prime
        primeList.add(numberTested);
        break;
    }
}

これの問題は何ですか？Math.sqrtコストのかかる操作です。乗算よりもはるかにコストがかかります...したがって、数値の範囲が許せば（常にそれを念頭に置く必要があります！）、乗算を使用して比較をより迅速に行うことができます。

sqrt(a)>b === a*a>baとbの両方が正の整数であると仮定します。

    Integer currentPrimeSquare = primeList.get(i)*primeList.get(i);
    if(currentPrimeSquare>numberTested) {
        //still not found a divider -- we found a prime
        primeList.add(numberTested);
        break;
    }

これをさらに調整するために、十分なメモリがある場合は、素数の平方も保存できます。

于 2013-02-28T12:48:45.187 に答える
1

Javaランタイムを比較するときに心配するVM自体のオーバーヘッドがあります（たとえば、printlnは実行ごとに異なる期間を取る可能性があります）。ランタイムを適切に比較するには、それぞれを1000回実行し、平均値を取得してより正確な結果を取得します。

また、 JavaでSieve of Erastothenesを実装することはそれほど難しくありませんが、より多くのメモリを使用しますが、非常に迅速な結果が得られます。

于 2013-02-28T12:52:32.983 に答える
0

与えられた数が素数であるかどうかを知るためにこれまでに知られている最も効率的なアルゴリズムに興味がある場合は、多対数時間で実行されるAKS素数性テストについて読むことを検討する必要があります。

（この回答は基本的に、素数性テストに関する質問に対する別の回答の繰り返しです。）

于 2013-02-28T12:59:34.430 に答える
0

1）素数を見つけるためにエラトステネスのふるいを使用することを検討しましたか？

2）実行時間を使用して効率を実際に測定するべきではありません

3）のifステートメントが素数であり、チェックしている場合はn = {2,3,5}それを使用して結果を返します。これにより、残りのコードを実行できなくなります（この場合はそれほど時間の節約にはなりません）

4）forループ、7（すでにチェックしている5の条件、6は素数ではない）からsqrt（n）までiに対して実行できます。

于 2013-02-28T13:21:15.377 に答える
-2

多分この記事はあなたを助けることができます：

boolean isPrime(int n) {
//check if n is a multiple of 2
if (n%2==0) return false;
//if not, then just check the odds
for(int i=3;i*i<=n;i+=2) {
    if(n%i==0)
        return false;
}
return true;
}
于 2013-02-28T12:50:22.803 に答える