4

割り当ては、p <= 31のすべてのメルセンヌ素数を見つけて、テーブルに表示することです。

p     2^p-1
---   ---- 
2      3

3      7

5      31

...

これまでの私の結果は次のコードです。

public class PE28MersennePrimeVer2 {

    public static void main(String[] args) {

        System.out.println("p\t2^p - 1");

        for (int number = 2; number <= 31; number++) {
            if (isPrime(number)) {
                int mersennePrime = (int)(Math.pow(2, number)) - 1;
                if (isPrime(mersennePrime)) {
                    System.out.print(number + "\t" + mersennePrime + "\n");
                }
            }
        }
    }

    public static boolean isPrime(int number) {

        if ((number == 1) || (number == 2)) {
            return true;
        }

        for (int i = 2; i <= number/2; i++) {
            if (number % i == 0) {
                return false;
            }
        }

        return true;
    }
}

出力はpが19までで、31に達することはありません。何が間違っているのでしょうか。

4

1 に答える 1

3

問題はそれです

(int)Math.pow(2,31) - 1;

2147483647ではなく2147483646に評価されます。

整数を扱うときは浮動小数点演算を使用しないでください。Javaでは、(1 << number) - 1動作を使用します（1 << 31オーバーフローが原因で、Cでは未定義の動作になりますが、Javaでは定義されています）。

ビットシフトを使用できない場合は、独自の整数べき関数を作成できます。検討中の小さな指数の場合、簡単です

long pow(long base, long exponent) {
    long result = 1;
    while(exponent > 0) {
        result *= base;
        --exponent;
    }
}

十分です（注：オーバーフローを回避するlong代わりに使用intしました。オーバーフローの動作はJavaで定義されていますが、オーバーフローを回避する方がクリーンです）。

それと、

mersennePrime = (int)(pow(2,number) - 1);

その仕事をします（ただしlong、中間結果だけでなく、他の変数にも使用することを検討する必要がありますpow）。

BigIntegerより大きな指数の場合（ただし、標準ライブラリに独自の実装があるsの使用、またはべき乗剰余にのみ関連します）、繰り返しの2乗によるべき乗

long pow(long base, long exponent) {
    long aux = 1;
    while(exponent > 0) {
        if (exponent % 2 == 1) {
            aux *= base;
        }
        base *= base;
        exponent /= 2;
    }
    return aux;
}

パフォーマンスに大きな利点があります。

于 2012-12-10T23:04:16.440 に答える