如何判断一个非常大的数是否是素数

本文关键字：是否是 非常 何判断 判断 一个 | 更新日期: 2023-09-27 18:09:54

我想弄清楚的数字是这样的形式(一些例子):

2 ^ 7 - 1, 2 ^ 31 - 1, 2 ^ 127 - 1，等等

这不是一个家庭作业问题，我只是在研究质数，很多信息都有点超出我的理解(傅里叶变换)。最初我只是使用这样一个函数:

public static bool IsPrime(int candidate)
{
    if ((candidate & 1) == 0)
    {
        return candidate == 2;
    }
    for (int i = 3; (i * i) <= candidate; i += 2)
    {
        if ((candidate % i) == 0)
        {
            return false;
        }
    }
    return candidate != 1;
}

但是一旦数字太大，这种方法就失效了。我还研究了埃拉托色尼筛子，但显然它只适用于小得多的数字。

澄清一下，我不是要写一个程序来查找素数，而是要确定给定的数字是否为素数。我正在研究。net框架中的BigInteger结构，如果我能写一个足够有效的算法(我愿意在几天内完成)，它看起来很有希望。

我不确定数学证明在这种情况下是否会更好，但我在这方面的知识并不多，而不是编程，但如果有专门针对这类数字的证明，那肯定值得一试。

谢谢。

如何判断一个非常大的数是否是素数

因数分解是件大事。它的困难是现代密码学的基础。

取决于你的数字有多大…你可以得到所有质数的列表直到你要找的数的平方根。这比每次上升2要小得多。问题是找到一个这么大的列表。如果你有一个数字是10^100，那么你需要所有小于等于10^50的质数，这仍然是一个很大的数字。

您列出的数字:2 ^ 7 - 1, 2 ^ 31 - 1, 2 ^ 127 - 1称为梅森数。已经有一个完整的分布式计算项目来找到这些。它叫做GIMPS。

所以你的问题的答案不是微不足道的。这里列出了所有已知的这种形式的质数:

http://en.wikipedia.org/wiki/Mersenne_prime List_of_known_Mersenne_primes

你的号码有上限吗?你说过你会将就几天。如果是这样，除非你的数字真的很大，否则你目前的算法是可以工作的。

你也可以看看Miller-Rabin素数检验

Java附带了一种概率素数测试的实现-参见Java .math. biginteger . isprobableprime()。我认为这意味着c#在语言中有类似的外观。我没有找到一个，但寻找一个，我发现一些代码在网上http://www.codeproject.com/KB/cs/biginteger.aspx.

相关文章：