6

My question is related to the following code:

public static void main(String[] args) {

    // Find Prime Numbers from 0 to 100
    int i;
    for (i=2; i <= 100; i++) {
        int j = 2;
        boolean iPrime = true;

        //The following line gives incorrect results, but should execute faster
        //  while ((iPrime = true) && (j < (i / 2 + 1))) {
        //The following line gives correct results but performs un-necessary operations
        //by continuing to calculate after the number is found to be "not prime"
        while (j < (i / 2 + 1)) {

            j++;
            if ((i % j) == 0) {
                iPrime = false;
                //System.out.println(j + " is a factor of " + i);
            }
        }
        if (iPrime) {
            System.out.println(i + " is a prime number!");
        }
    }
}

Now, as I've commented in the code, what I'm trying to achieve is a faster execution of my program by executing the 'while' loop only when iPrime = true. 50% of numbers are divisible by 2 and so this once this has been established the calculations can stop.

I'm doing this project as part of a beginners 'example' from a book, I actually am trying to calculate up to 1000000 as quickly as possible just for my own "extra credit"...

I read that the "short circuit 'and' operator" && only evaluates the second half of the statement if the first half is true, if it is false, the two are not evaluated against each other (saving CPU)

And it will also exit the loop, which will save even more CPU...

But for some reason, it is not working correctly! I've put more System.out.println() statements throughout, listing what 'iPrime' is - and the output is stranget... It switches iPrime on and off and evaluates every number, which I cannot understand.

4

4 に答える 4

7

if((iPrime = true) && ...)する必要がありますif((iPrime) && ...)。

そうすることで、 trueをisPrime = trueに割り当て、その値をと比較isPrimeしません。true

コードで何が起こっているかをよりよく理解するために、これを確認することもできます。

実行時の代入式の結果は、代入が行われた後の変数の値です。代入式の結果自体は変数ではありません。

したがって、=代わりに演算子を使用すると==(これは何かを比較すると削除されますtrue- 書く代わりに、if(someBoolean == true)単に書くだけです)、実際には常にif(someBoolean)条件を満たしています!

于 2013-04-20T13:56:09.803 に答える
4

に変更=するだけ==です。

while ((iPrime = true) && (j < (i / 2 + 1)))

の中へ

while ((iPrime == true) && (j < (i / 2 + 1)))

パフォーマンスが向上した完全なコード

public static void main(String[] args) {
    // Find Prime Numbers from 0 to 100
    System.out.println(2 + " is a prime number!");
    for (int i = 3; i <= 100; i += 2) {
        boolean isPrime = true;
        for (int j = 3; j * j <= i; j += 2) {
            if ((i % j) == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) {
            System.out.println(i + " is a prime number!");
        }
    }
}

私が考えることができる最速の方法は、エラトステネスのふるいです。

于 2013-04-20T13:54:34.813 に答える
1

johnchen902 / Maroun Maroun がバグを修正しました。さらに、実行できる最適化は次のとおりです。

System.out.println("2 is a prime number!"); // the for loop won't detect 2 anymore
for (i=3; i <= 100; i+=2) {

また、先行するすべての奇数を含む数値に対してモジュロ演算子を実行して素数であるかどうかを確認する代わりに、先行するすべての素数を含む数値に対してモジュロ演算子を実行して、素数であるかどうかを確認できます。たとえば、見つけた素数を ArrayList に格納し、素数テストでリストを反復処理します。

また、CPU 効率が非常に高い (ただしスペース効率が低い) アルゴリズムの場合は、エラトステネスのふるいを使用します。

于 2013-04-20T14:00:21.637 に答える
1

最初にコードを実行すると、4 が正しくない素数として表示されることがわかりました。その理由は、j++ 行の場所です。while ループを次のように変更する必要があります。

while (j < (i / 2 + 1)) {   
                if ((i % j) == 0) {
                    iPrime = false;

                    //System.out.println(j + " is a factor of " + i);
                    break;
                }
                j++;
            }

2 番目の部分に移ると、数が素数ではないことを確認したときに余分な計算を避ける必要があります。上記のコードのように、これには break ステートメントを使用できます。

等価比較の代わりに割り当てがあるため、コメント部分は機能しません。

于 2013-04-20T14:02:06.337 に答える