-1

プログラムに素数の種類を実装しようとしています。メルセンヌの指数タイプの1つでは、計算式は(2 power P) -1HereでP is Prime.あり、出力が素数であることを確認します。

計算では、パワーを得ることができますが、素数をチェックしている間、プロセスはハングしています。そして、私がそれを非常に長い間放置すると、それは計算されています。

例は、（2 power 10090）-1であり、これがプライムであるかどうかを計算します

ビッグ整数を使用しています

私はこのコードをいじっています

int prime1 = CalculatePrime(n);
BigInteger powerPrime = BigInteger.Pow(2, prime1);
bool isPrime = CheckPrime(powerPrime - 1);

private bool CheckPrime(BigInteger num)
{
    if (num == 0 || num == 1) 
        return false;

    bool isPrime = true;
    for (int j = 2; j < num; j++)
    {
        if ((num % j) == 0)
        {
            isPrime = false;
            break;
        }
    }
    return isPrime;
}

これはどうでしょうか-http://www.dotnetperls.com/prime

4

3 に答える 3

1

エラトステネスのふるいは、数百万未満の素数を生成するための特に優れたアルゴリズムです。

于 2013-02-27T18:37:51.487 に答える
1

Lucas-Lehmer 検定は、メルセンヌ数が素数であるかどうかのチェックに特化しています。実装したテストよりも優先して使用する必要がありますが、これは非常に遅くなる可能性があります。

于 2013-02-27T18:46:08.727 に答える
0

次の理由により、作業を少し減らすことができます。

  1. のみをチェックする必要がありますj < sqrt(num)。j < num
  2. すべての偶数をチェックする必要はありません: 最初に 2 で試してから、奇数のみをチェックしてください (これは、すべての偶数が 2 で割り切れるためです。したがって、x が 2 で割り切れない場合、x はどの数字でも割り切れないためです)。その他偶数）
于 2013-02-27T18:40:24.403 に答える