-1

我正在尝试在我的程序中实现素数类型。在 Mersenne 的指数类型之一中，计算公式为(2 power P) -1HereP is Prime.并检查输出是否为素数。

在计算中，我能够获得力量，但在检查素数时，过程是 Hanging 。如果我离开它很长时间，那么它正在被计算。

例如， (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 整除，它就不能被任何其他偶数）
于 2013-02-27T18:40:24.403 回答