素性检查可能是数学中“那些”棘手的问题之一。那么，什么是最好和最快的算法来检查一个巨大的数字的素性。最粗暴和最慢的方式可能是:
public static bool IsPrime(int i)
{
for (var x = 2; x < i - 1; i++)
{
if (i % x == 0)
{
return false;
}
}
return true;
}
最近看到768位RSA算法被暴力破解，使用网格计算阵列。他们如何对一个巨大的素数进行暴力破解？每个处理单元是否占用一系列数字，将其分解并检查该范围内所有数字的素数？
最佳答案
查看 primality tests在维基百科上获取指向当前算法的指针
关于您的天真实现，请注意，如果数字可以被 2 整除，您可以立即返回 false，这样您就可以只检查奇数。另外，如果你没有找到 x <= sqrt(i) 的因子，它就是质数。这是因为如果您确实找到了一个大于 sqrt(i) 的因子，那么它必须与一个小于 小于 sqrt(i) 的因子配对。因此，如果您没有首先找到那个较小的因素，那么您就完了。
在您必须成群结队前往 https://mathoverflow.net/ 之前，您还可以将更多技巧应用于朴素算法。寻求帮助:)
关于algorithm - 素数校验算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2055300/